下一个排列

下一个排列

• n个元素有n!种排列方式，你不会想都罗列出来再去找下一个排列吧
• 这种排序方式为字典序，字典序就是将元素按字典的顺序进行排序
• 针对这个串生成全排列，就是依次生成"12345"→"12354"→"······"→"54321"
• 字典序法要求这一个与下一个排列有尽可能长的共同前缀，也即变化限制再尽可能短的后缀上，以<6,2,1,5,4,3,0>为例，<5,4,3,0>是最长降序序列（后缀），直觉上应该将1和3交换位置，以对前缀产生尽可能小的影响，现在我们的序列是<6,2,3,5,4,1,0>,<6,2,3>我们的前缀现在是最小的，这点毫无疑问，但后缀不一定是最小的。后缀交换前是降序的，交换后也是降序的，所以现在只需要简单翻转即可。

    public void nextPermutation(int[] nums) {
        if (nums.length == 0 || nums == null) return;
        int k = nums.length - 2;
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            --k;
        }
        if (k == -1){
            reverse(nums,0);
            return;
        }
        for (int i = nums.length - 1; i > k; i--) {
            if (nums[i] > nums[k]) {
                int temp = nums[i];
                nums[i] = nums[k];
                nums[k] = temp;
                break;
            }
        }
        reverse(nums, k + 1);
    }

    static void reverse(int[] nums, int start) {
        int end = nums.length - 1;
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

Tips:

• 代码比较繁琐，给你的不是集合，只能自己写一个反转数组的函数，而且示例还可能出现重复元素，需要考虑边界情况
• 时间复杂度为O(N)，不需要额外存储空间