Next Permutation

description:

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.

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

Thoughts;
要找到比原来大的最小的字典序，我们把这个数组分成两个部分来看，前一个部分它是杂乱的，后一个部分的数字单调递减。比原始数组稍大的字典序就是将杂乱部分的最高位的数字和递减序列中第一个比它大的数字对换，然后将原来的的单调递减序列（对换之后也是单调递减序列，因为对换过来的数字会至少比所对换的数字原来所在的位置的前面的数字想小，比它后面的数字大）变成变成单调递增序列。新形成的这个序列就是我们想要的序列。这里要注意单独讨论原始数组是单调递减的情况，此时只需要直接将序列变成递减序列。

以下描述参考自leetcode中@yuyibestman的解释

My idea is for an array:

1. Start from its last element, traverse backward to find the first one with index i that satisfy num[i-1] < num[i]. So, elements from num[i] to num[n-1] is reversely sorted.
2. To find the next permutation, we have to swap some numbers at different positions, to minimize the increased amount, we have to make the highest changed position as high as possible. Notice that index larger than or equal to i is not possible as num[i,n-1] is reversely sorted. So, we want to increase the number at index i-1, clearly, swap it with the smallest number between num[i,n-1] that is larger than num[i-1]. For example, original number is 121543321, we want to swap the '1' at position 2 with '2' at position 7.
3. The last step is to make the remaining higher position part as small as possible, we just have to reversely sort the num[i,n-1]

这是我的java代码

package middle;

import java.util.Arrays;

public class NextPermutation {
    public void nextPermutation(int[] nums){
        if(nums.length >= 2){
            int position = nums.length - 1;
            int i = position - 1;
            while(i>=0){
                if(nums[i]>= nums[i+1]){
                    i--;
                }else{
                    break;
                }
            }
            if(i == -1){
                for(int j = 0; j<=((nums.length - 1)/2);j++){
                    int num = nums[nums.length - 1- j];
                    nums[nums.length -1 -j] = nums[j];
                    nums[j] = num;
                }
            }else{
                for(int j = position; j >i; j--){
                    if(nums[j] > nums[i]){
                        int num = nums[j];
                        nums[j] = nums[i];
                        nums[i] = num;
                        break;
                    }
                }
                for(int j = i+1; j<=(i+1+nums.length-1)/2;j++){
                    int num = nums[nums.length - 1 + i +1 -j];
                    nums[nums.length -1 +i+1-j] = nums[j];
                    nums[j] = num;
                }
            }
            
        }
    }
    
    public static void main(String[] args){
        NextPermutation n = new NextPermutation();
        int[] nums = new int[]{3, 2, 1};
        n.nextPermutation(nums);
        for(int i = 0;i< nums.length ;i++){
            System.out.println(nums[i]);
        }
    }
}