med题记录31

题目描述

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

思路

重点在于找到一个断点——从后往前遍历，一旦有下降，就是断点。例如：

2 1 5 4 3 0 0

此时断点是1。找到断点后，只需把断点和后面的最小值互换：

2 3 5 4 1 0 0

然后再反转断点下标之后的部分：

2 3 0 0 1 4 5

就得到了下一个排列。如果找不到断点，即这个数组从后往前遍历没有任何下降，说明此时已经是最大的字典序，直接返回reverse。

这样做的原理是：要找到下一个字典序，重点在于“要动哪一位”。只有这一位后面的东西已经尽可能大（降序排列），才需要让这一位换成一个更大的数，且把后面的排列换成最小字典序。这个过程可以用加法进位理解。

知道了要动哪一位，下一个问题就是“换成几”。下一个字典序要保证不能跳位，也就是必须换成尽可能小的更大的值，从后往前遍历，直到找到一个比断点更大的值，直接换。为什么从后面选而不考虑前面会有更小的值呢？因为字典序的排序顺序要求必须从后往前找最小值，前面的东西还没轮到它们参与排序，等遍历到它们之后，它们会作为新的断点。

完整代码

/**
 Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums: number[]): void {
    let break_idx = -Infinity;
    for(let i = nums.length - 2; i >= 0; i--) {
        if(nums[i] < nums[i + 1]) {
            break_idx = i;
            break;
        }
    }
    if(break_idx < 0) {
        nums = nums.reverse();
        console.log(nums);
        return;
    }

    // console.log(break_idx);

    for(let i = nums.length; i > break_idx; i--) {
        if(nums[i] > nums[break_idx]) {
            let k = nums[i];
            nums[i] = nums[break_idx];
            nums[break_idx] = k;
            break;
        }
    }
    
    // console.log(nums);

    let end = nums.length - 1;
    let start = break_idx + 1;

    while(end >= start) {
        let k = nums[end];
        nums[end] = nums[start];
        nums[start] = k;
        end--;
        start++;
    }

    console.log(nums);    
};

nextPermutation([1, 3, 2]);