Next Permutation

问题描述

　　找出数组的下一个排列数组，如：
　　　　　　　　　　　　　　　　　　　　　　　　1,2,3 -> 1,3,2
　　　　　　　　　　　　　　　　　　　　　　　　1,1,5 -> 1,5,1

　　分析后发现，这里的全排列可以组成这样的一个循环，比如：
　　　　1,2,3 -> 1,3,2 -> 2,1,3 -> 2,3,1 -> 3,1,2 -> 3,2,1 -> 1,2,3

唯一要求

　　必须原地修改，只允许使用额外常数空间。

解题思路

　　  从后往前遍历，找到降序的位置，如果整个序列没有降序的位置，例如 3，2，1，则直接返回升序序列。如果有降序情况，记录下标为 j，然后再次从后往前找到第一个大于 nums[j] 的值，交换这两个元素的值 ，将下标 j + 1 及往后的序列升序 即得到下一个排列。

public class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int j = -1;
        for (int i = n - 2; i >= 0; i --) {
            if (nums[i] < nums[i + 1]) {
                j = i;
                break;
            }
        }
        if (j == -1) {
            Arrays.sort(nums);
            return;
        }
        for (int k = n - 1; k > j; k --) {
            if (nums[k] > nums[j]) {
                int tmp = nums[k];
                nums[k] = nums[j];
                nums[j] = tmp;
                break;
            }
        }
        // reverse j+1 - end
        reverse(nums, j + 1, n - 1);
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int tmp = nums[r];
            nums[r] = nums[l];
            nums[l] = tmp;
            l ++;
            r --;
        }
    }
}