31. Next Permutation

Tags

1. Array

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

题意：

实现再排列，意思就是重新将数字排列到比它更大的数字的序列上。 如果这种安排是不可能的，那必须按照把它作为可能的最小顺序进行重排（即按升序排序）。 替换必须在原数组上替换，不能分配其它额外的内存。

分析：

刚开始拿到这道题的时候，完全没懂什么意思。后面看了其它语言的实现，感觉明白了一点。解释下来就是，找到数组中第一个后面数字比前面数字大的数，然后互相换位置，然后将后面的数进行升序排列（我的理解，也不知道对不对）。所以，js实现是按照其它语言的实现代码改造过来的。

思路：

基本思路按照代码说就是

1. 倒序找到当前数字比前面数字大的位置i
2. 以i为起点找到后面数字比它大的数字位置j
3. 交换这两个数的位置
4. 将i之后的数字进行升序排序

复杂度：

时间复杂度O(n)

Js实现：

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

function swap(nums, i, j){
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

function reverse(nums, i, j){
    while(i < j) {
        swap(nums, i++,j--);
    }
}