LC 31 Next Permutation(M)

mplement 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

边界条件 数组只是有两个或以上的值

解题思路

方法是从后向前找顺序的值(n[i]<n[i+1],假定当前已经是逆序数组)，找到第一个inversion，如上例中，然后继续从后向前判断，假如从数组尾部到i元素 间第一个数字大于i， 则swap i 和这个数字，由于swap之后依然是倒序，所以我们reverse i 到 nums.length -1。

Time Complexity - O(n)， Space Complexity - O(1)。

public void nextPermutation(int[] nums) {
    if(nums == null || nums.length < 2){
        return;
    }
    int len = nums.length;
    // find first n[i] < n[i+1]
    for(int i = len - 2; i>=0; i--){
        if(nums[i] < nums[i+1]){
            // find from end first n[j] > n[i]
            for(int j = len - 1; j>i; j--){
                if(nums[j]> nums[i]){
                    swap(nums, i, j);
                    reverse(nums, i+1, len -1);
                    return;
                }
            }
        }
    }
    reverse(nums, 0, len - 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 l, int h){
    while(l<h){
        swap(nums, l++, h--);
    }
}