leetcode 31 Next Permutation

binaryTree 发布于2019-08-19 10:41 / 814人阅读

摘要：我们所找到的这个元素就是排序需要改变的第一个元素。然后我们选取一个刚好大于此元素的数，与当前元素进行替换。并对后面的所有元素重新按照升序排列就可以得到最终的答案。

题目详情

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.

题目的意思是找到当前元素排列的‘下一个排列’。那么什么叫‘下一个排列呢’？这里举个例子，比如说元素1，2，3。它们的全排列是‘1，2，3’，‘1，3，2’，‘2，1，3’，‘2，3，1’，‘3，1，2’，‘3，2，1’因此比如求‘123’的下一个排列，就应该返回‘1，3，2’.
如果当前的序列不存在‘下一个排列’，那么就返回完全升序的第一个排列。

例子：左侧一列是输入，右侧是正确的输出：
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

想法

当我们要求一个排列的‘下一个排列’，我们需要意识到问题的关键在于从数组末端遍历到的，第一个不满足nums[i] <= nums[i+1]条件的元素。

我们所找到的这个元素就是排序需要改变的第一个元素。

然后我们选取一个刚好大于此元素的数，与当前元素进行替换。并对后面的所有元素重新按照升序排列就可以得到最终的答案。

我描述的不是很清晰，这里引用一张leetcode上的图讲解

解法

    public void nextPermutation(int[] nums) {
        int length = nums.length;
        int i= length-2;
        while(i>=0 && nums[i+1] <= nums[i])i--;
        if(i >= 0){
            int j = length -1;
            while(j >= 0 && nums[j] <= nums[i])j--;
            swap(nums,i,j);
        }
        reverse(nums,i+1);
    }
    
    public void reverse(int[] nums,int start){
        int end = nums.length-1;
        while(start < end){
            swap(nums,start,end);
            start ++;
            end --;
        }
    }
    
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

云服务器 GPU云服务器 Permutation Leetcod LeetCode -next

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

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

leetcode31 Next Permutation

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

hedzr 2019-08-16 10:34 评论0 收藏0
31. Next Permutation

摘要：边界条件，这时候之后只有一个值数组一直递减，这时候变成，没有，只需要从到的所有数。 31. Next Permutation 题目链接：https://leetcode.com/problems... 这道题就是找规律，可以看出来下一个permutation的规律是：从右往左扫，找到第一个满足：nums[i-1] < nums[i]条件的，再找到从右到左第一个比nums[i-1]大的数...

未东兴 2019-08-14 17:26 评论0 收藏0
[Leetcode] Next Permutation 下一个排列

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

young.li 2019-08-14 12: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
31. Next Permutation

摘要：比如我们很容易知道下一个数字是。从尾到头找，第一段的部分出现。后面的部分就可以有更大的组合。这里是在递减序列中找到下一个比大的数字，作为序列的头。尾部的递减序列变成递增序列。 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation o...

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