---

0031. 下一个排列

• 标签：数组、双指针
• 难度：中等

题目链接

• 0031. 下一个排列 - 力扣

题目大意

描述：

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

• 例如，$arr = [1,2,3]$，以下这些都可以视作 $arr$ 的排列：$[1,2,3]$、$[1,3,2]$、$[3,1,2]$、$[2,3,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 \le nums.length \le 100$。
• $0 \le nums[i] \le 100$。
• 必须原地修改，只允许使用额外常数空间。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：暴力搜索

核心思想：从右向左遍历数组，找到第一个可以交换的位置，然后交换并排序剩余部分。

算法步骤：

1. 从数组末尾开始向前遍历，找到第一个 $nums[i] < nums[j]$ 的位置（其中 $j > i$）。
2. 找到这个位置后，交换 $nums[i]$ 和 $nums[j]$。
3. 将 $nums[i+1:]$ 部分进行排序，得到字典序最小的排列。
4. 如果找不到这样的位置，说明当前排列已经是最大排列，直接对整个数组排序得到最小排列。

关键点：

• 从右向左遍历确保找到的是最右边的可交换位置。
• 交换后对剩余部分排序，保证得到的是下一个字典序排列。

思路 1：代码

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        size = len(nums)
        for i in range(size - 1, -1, -1):
            for j in range(size - 1, i, -1):
                if nums[i] < nums[j]:
                    nums[i], nums[j] = nums[j], nums[i]
                    nums[i + 1: ] = sorted(nums[i + 1:])
                    return
        nums.sort()

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是数组长度。最坏情况下需要遍历所有位置，每次遍历需要 $O(n)$ 时间，排序需要 $O(n \log n)$ 时间。
• 空间复杂度：$O(1)$，只使用了常数额外空间。