31. 下一个排列

[S-T-D]

• 原题地址
• 题目描述
• 题解
  • 思路
  • 代码
  • 复杂度
     

原题地址

31. 下一个排列

 

题目描述

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

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

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

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]

示例 4：
输入：nums = [1]
输出：[1]
 
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100

 

题解

思路

代码

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    // 1 2 3 4 5 7 6 4 => 1 2 3 4 6 4 5 7
    const len = nums.length;

    // 1. 从后往前找到第一个相邻的升序对
    let end = len - 1;
    let ascendPairLeft = -1, ascendPairRight = -1;
    while (end > 0) {
        if (nums[end - 1] < nums[end]) {
            ascendPairLeft = end - 1;
            ascendPairRight = end;
            break;
        }
        end--;
    }

    // 2. 如果没有升序对，说明 nums 是降序排列，已经是最大值
    if (ascendPairLeft === -1) {
        nums.reverse();
        return;
    }

    // 3. [ascendPairRight, end) 一定是降序，在 [ascendPairRight, end) 中找第一个大于 nums[ascendPairLeft] 的数
    end = len - 1;
    let tar = -1;
    while (end > ascendPairRight) {
        if (nums[end] > nums[ascendPairLeft]) {
            tar = end;
            break;
        }
        end--;
    }

    // 4. 交换 ascendPairLeft 和 tar
    tar = tar !== - 1 ? tar : ascendPairRight;
    [nums[tar], nums[ascendPairLeft]] = [nums[ascendPairLeft], nums[tar]];
    
    // 5. [ascendPairRight, end) 目前是降序，倒序使其变成升序
    let left = ascendPairRight, right = len - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};

复杂度

• 时间：O(n)
• 空间：O(1)