实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。

如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

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

解析:

找到输入数组字典序中的下一个位置,感觉像是找规律一样..... (可以多举几个例子,找一下其中的共同点) 比如1,2,3,4,5的下一个字典序为1,2,3,5,4 可以看到只改变了最后两个数字,因为整个序列都是升序的

再比如1,5,4,3,2的下一个字典序为2,5,4,3,1 可以看到5,4,3,2是降序的,就需要找到比1的大的最小数字2,和1交换位置,然后后面的升序排序

于是,从中总结出规律,需要先找到左右两个下标left和right,left表示最后一组的升序数字的第1个,right表示left后面的数字中比l大的最靠右的数字,比如
1,2,3,4,5 -> left = 4 , right = 5
1,5,4,3,2 -> left = 1 , right= 2
然后,将left和right位置的数字交换,交换后,对left后面部分的数字进行升序排序即可

Java:

class Solution {
    public void nextPermutation(int[] nums) {
        int left = 0, right = nums.length - 1;
        for(int i = 0; i < nums.length - 1; i++) {
            if(nums[i] < nums[i + 1]) {
                left = i;
            }
        }
        for(int i = left + 1; i < nums.length; i++) {
            if(nums[i] > nums[left]) {
                right = i;
            }
        }
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        Arrays.sort(nums, left + 1, nums.length);
        return;
    }
}

JavaScript:

var nextPermutation = function(nums) {
    let left = 0, right = nums.length - 1;
    for(let i = 0; i < nums.length - 1; i++) {
        if(nums[i] < nums[i + 1]) {
            left = i;
        }
    }
    for(let i = 0; i < nums.length; i++) {
        if(nums[i] > nums[left]) {
            right = i;
        }
    }
    let temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
    let arr = nums.slice(left+1);
    arr.sort((a,b) => a - b);
    nums.splice(left+1,nums.length - left, ...arr);
    return;
};