Medium

题目描述

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3]，以下是 arr 的所有排列：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]。

数组的下一个排列是其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2]。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3]，因为 [3,2,1] 不存在字典序更大的重排。

给你一个整数数组 nums，找出 nums 的下一个排列。

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解题思路

这是一个经典的算法问题，需要深入理解字典序排列的规律。

核心思路： 要找到下一个字典序更大的排列，关键是找到需要调整的位置。观察规律可知：

  1. 从右向左扫描，找到第一个 nums[i] < nums[i+1] 的位置 i（称为"较小数"）
  2. 如果找不到这样的 i，说明当前序列是最大排列，直接反转整个数组
  3. 如果找到了位置 i，再从右向左找到第一个大于 nums[i] 的数 nums[j]（称为"较大数"）
  4. 交换 nums[i] 和 nums[j]
  5. 将位置 i+1 到末尾的部分反转，使其变为最小排列

算法步骤详解：

  • 步骤1确保我们找到了需要"提升"的位置，这个位置左边的部分在新排列中保持不变
  • 步骤3确保交换后 nums[i] 位置的值尽可能小，但仍然大于原来的值
  • 步骤5确保 i+1 之后的部分是最小排列，这样整体排列就是下一个字典序排列

这个算法的巧妙之处在于，它直接找到了需要调整的关键位置，避免了枚举所有排列的低效做法。

代码实现

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 2;
        
        // 找到第一个nums[i] < nums[i+1]的位置
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            // 找到第一个大于nums[i]的数
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // 交换
            swap(nums[i], nums[j]);
        }
        
        // 反转i+1到末尾的部分
        reverse(nums.begin() + i + 1, nums.end());
    }
};

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = n - 2
        
        # 找到第一个nums[i] < nums[i+1]的位置
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        
        if i >= 0:
            # 找到第一个大于nums[i]的数
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            # 交换
            nums[i], nums[j] = nums[j], nums[i]
        
        # 反转i+1到末尾的部分
        nums[i + 1:] = nums[i + 1:][::-1]

public class Solution {
    public void NextPermutation(int[] nums) {
        int n = nums.Length;
        int i = n - 2;
        
        // 找到第一个nums[i] < nums[i+1]的位置
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            // 找到第一个大于nums[i]的数
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // 交换
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        // 反转i+1到末尾的部分
        Array.Reverse(nums, i + 1, n - i - 1);
    }
}

var nextPermutation = function(nums) {
    const n = nums.length;
    let i = n - 2;
    
    // 找到第一个nums[i] < nums[i+1]的位置
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) {
        // 找到第一个大于nums[i]的数
        let j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        // 交换
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    
    // 反转i+1到末尾的部分
    let left = i + 1, right = n - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)最多扫描数组3次：找较小数、找较大数、反转操作
空间复杂度O(1)只使用常数额外空间，原地修改数组

相关题目