[Leetcode] Next Permutation 下一个排列

young.li 发布于2019-08-14 12:34 / 2139人阅读

摘要：因为增加高位会带来更大的增益。所以对于一个长为的序列，我们增加第位的前提是，前位已经达到了最大排列方法。因为是找下一个数，所以我们要找一个比小却尽可能大的数，所以找到。把换到的位置后，后三位仍然是个降序的排列。

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

升序倒置法 复杂度

时间 O(N) 空间 O(1)

思路

首先我们来思考下，什么是next permutation
比如124651这个序列，我们如果只想它变大一点点，应该尽可能的不去增加高位。因为增加高位会带来更大的增益。所以对于一个长为n的序列，我们增加第n位的前提是，前n-1位已经达到了最大排列方法。所以我们从后往前看：

1
51
651

前面三位已经是各自最大的情况，不可能再变大，而到万位的时候4651，可以将4移到后面来来增大。但是问题在于，把谁移到4的位置。因为是找下一个数，所以我们要找一个比4小却尽可能大的数，所以找到5。把5换到4的位置后，后三位仍然是个降序的排列。然而这时候，因为已经将万位增大了，我们要将前三位尽可能的变小，做成一个以5开头最小的序列，而这个序列应该是升序的，所以我们直接把后三位倒置一下，就从降序变成升序了。

注意

找第一个下降点的循环和着第一个比下降点稍大的数的循环，其判断条件都要包含=

代码

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length <= 1){
            return;
        }
        int i = nums.length - 2;
        // 找到第一个下降点，我们要把这个下降点的值增加一点点
        // 对于511这种情况，要把前面两个1都跳过，所以要包含等于
        while(i >= 0 && nums[i] >= nums[i + 1]){
            i--;
        }
        // 如果这个下降点还在数组内，我们找到一个比它稍微大一点的数替换
        // 如果在之外，说明整个数组是降序的，是全局最大了
        if(i >= 0){
            int j = nums.length - 1;
            // 对于151，这种情况，要把最后面那个1跳过，所以要包含等于
            while(j > i && nums[j] <= nums[i]){
                j--;
            }
            swap(nums, i, j);
        }
        // 将下降点之前的部分倒序构成一个最小序列
        reverse(nums, i + 1, nums.length - 1);
    }
    
    private void swap(int[] nums, int i, int j){
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;
    }
    
    private void reverse(int[] nums, int left, int right){
        while(left < right){
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

GPU云服务器云服务器 Permutation 下一个节点 LeetCode 抖音自动播放下一个视频

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64561.html

leetcode 31 Next Permutation

摘要：我们所找到的这个元素就是排序需要改变的第一个元素。然后我们选取一个刚好大于此元素的数，与当前元素进行替换。并对后面的所有元素重新按照升序排列就可以得到最终的答案。题目详情 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of...

binaryTree 2019-08-19 10:41 评论0 收藏0
leetcode31 Next Permutation

摘要：如果当前数字代表的整数值已经是所有排列组合中的最大值，则返回当前数字组成的最小值。可是这意味着大量无用的数字的生成和比较。一个数字中的各个位上的数如何调整顺序才能获得一个最小的更大值。其次，要保证移动之后，高位以后的值为最小值。题目要求 Implement next permutation, which rearranges numbers into the lexicographi...

hedzr 2019-08-16 10:34 评论0 收藏0
[Leetcode]PermutationsI II Next Permutation Permut

摘要：解题思路这道题是要将排列按字典序排列，然后求出下一个排列，一种办法是我们先求出所有的排序情况，但是题目规定不能占有额外空间。每次求出一个数字后，要及时的把它从中删除掉。采用来构造结果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

ChristmasBoy 2019-08-16 10:26 评论0 收藏0
[Leetcode] Permutation Sequence 全排列序列

摘要：找规律复杂度时间空间思路由于我们只要得到第个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律假设全排列有个数组成，则第个全排列的第一位是。然后将得到，这个就是下一轮的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 评论0 收藏0
leetcode46 Permutation 排列组合

摘要：题目要求也就是得出所有可能的排列组合结果解题思路和代码这题显然采用递归的思路。在这里，我采用实现队列，从队列头获得上一组的结果，和当前元素结合之后，将结果插入到队尾。题目要求 Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the ...

wendux 2019-08-16 10:34 评论0 收藏0