[leetcode javascript解题]Next Permutation

我会带着你远行 2022-07-13 03:59 142阅读 0赞

leetcode 第31题 “Next Permutation”描述如下，有点长：

> 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`

题意其实有点难理解，其实意思是按字典顺序输出它的下一个序列，如果没有， 就输出最小序列。其实意思就是比如你是1，2，3。输出就应该是比1，2，3组合大一点的，1，3，2。你是1，3，4，5，6。输出就应该是1，3，4，6，5 这样，如果是3，2，1这种从大到小的，没有更大的组合，就输出最小组合1，2，3。同时题目限制了只能在原有数组上操作，不允许使用额外空间。  
算法流程是这样的：  
1、从右往左找，直到找到一个i使`nums[i-1]<nums[i]`。  
2、第二次从右往左遍历，找到比`nums[i-1]`大，但和他相差最小的那个数，交换他们的位置。  
3、从索引i到length-1位置，按从小到大重新排列，因为实际上从i到ength-1位置原本是从大到小排列的（原因请看步骤1），所以可以以正中间的哪个数为界，左右两边两两交换位置，减少计算次数。

思路其实就是类似于进位原理，越左边的数看成越高位，相当于i-1位的值升高，i-1位后的所有位处在值最低的状态，就相当于输出了相较当前序列，上升最少的序列。

/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */
    var nextPermutation = function(nums) {
        if (nums.length <= 1) {
            return;
        }
        var len = nums.length,
            i = len - 1;
        while (i > 0) {
            if (nums[i - 1] < nums[i]) {
                break;
            }
            i--;
        }
        var j = len - 1,
            temp;
        if (i > 0) {
            while (j > i - 1) {
                if (nums[j] > nums[i - 1]) {
                    temp = nums[i - 1];
                    nums[i - 1] = nums[j];
                    nums[j] = temp;
                    break;
                }
                j--;
            }
        }
        j = 0;
        while (j + i < Math.ceil((i + len - 1) / 2)) {
            temp = nums[len - 1 - j];
            nums[len - 1 - j] = nums[j + i];
            nums[j + i] = temp;
            j++;
        }
        return;
    };