31. Next Permutation

denson 发布于2019-08-16 10:34 / 1605人阅读

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

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
1,7,6,5,4,3 -> 3,1,4,5,6,7
7,6,5,8,3 ->  7,6,8,3,5

这里实际上是找下一个更大的数字。比如1,2,3 我们很容易知道下一个数字是1,3,2。
从尾到头找，第一段ascending的部分出现。后面的部分就可以有更大的组合。

  i        
9 1 7 5 4 3
          j  
9 3 7 5 4 1
    i+1
9 3 1 4 5 7

  i
9 6 7 5 4 3
    j
9 7 6 5 4 3
    i+1
9 7 3 4 5 6

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length <= 1) return;
        
        int i = nums.length - 2;
        
        // 找到尾部的第一段递减序列。
        while(i >= 0 && nums[i] >= nums[i+1]){
            i--;
        }
        
        if(i >= 0){
            int j = nums.length - 1;
            // 这里是在递减序列中找到下一个比nums[i]大的数字，作为序列的头。
            while(i < j && nums[j] <= nums[i]){
                j--;
            }
            swap(nums, i, j);
        }
        // 尾部的递减序列变成递增序列。
        reverse(nums, i+1, nums.length-1);
        
    }
    
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void reverse(int[] nums, int i, int j){
        while(i < j){
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

GPU云服务器云服务器 Permutation -next Next next.js

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

转载请注明本文地址：https://www.ucloud.cn/yun/70031.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
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
leetcode31 Next Permutation

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

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

摘要：从末位向前遍历，假设循环开始全是倒序排列，如当第一次出现正序的时候，如的和此时从数列末尾向前循环到，找到第一个比大的交换这两个数，变成倒置第位到末位的数为正序排列这里的是完全倒置的排列，如，即上面循环的情况完全没有出现， Problem Implement next permutation, which rearranges numbers into the lexicographic...

mikasa 2019-08-14 15:15 评论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