下一个排列 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

引入

整数 $13999$ 的「下一个整数」是多少？

你可以轻松地答出： $14000$ 。

怎么算的？拆解步骤：

从右到左，找第一个可以增大的数字（小于 $9$ 的数字），即 $3$ 。
把 $3$ 加一，变成 $4$ 。
把 $4$ 右边的数都变成 $0$ 。

本题要计算「下一个排列」，这类似于计算「下一个不含重复数字的整数」，计算框架应该和「下一个整数」是类似的，具体要怎么做呢？

例子

排列 $[1, 3, 5, 4, 2]$ 的下一个排列是什么？

从右到左，找第一个可以增大的数。什么是「可以增大的数」？

如果 $1, 3, 5$ 保持不变，只重新排列 $4, 2$ ，得到 $2, 4$ 。排列变小了，这不行。
如果 $1, 3$ 保持不变，只重新排列 $5, 4, 2$ ，由于 $5$ 的右边都是小于 $5$ 的数，所以重排后， $5$ 这个位置上的数必然变小，导致排列变小，这也不行。
如果 $1$ 保持不变，只重新排列 $3, 5, 4, 2$ ，这是可以的，因为 $3$ 右边有比 $3$ 大的数，重排后可以让 $3$ 这个位置上的数变大，从而得到更大的排列。
由于要求的是下一个排列，所以 $3$ 这个位置上的数只要「大一点点」就好了。找到 $3$ 右边最小的大于 $3$ 的数，也就是 $4$ ，放到 $3$ 这个位置上。于是，下一个排列是 $[1, 4,_,_,_]$ 。
剩余的三个数是 $2, 3, 5$ 。由于只看前两位 $[1, 4,_,_,_]$ 就已经比 $[1, 3, 5, 4, 2]$ 大了，所以后三位填最小的排列就行，即按照 $2, 3, 5$ 的顺序填，得到 $[1, 4, 2, 3, 5]$ 。

回顾我们是怎么算的：

从右到左，找第一个可以增大的数 $x$ ，也就是 $x$ 右边有大于 $x$ 的数。我们找到的数是 $3$ 。由于 $3$ 右边的数是递减的（证明见答疑），所以 $3$ 右侧相邻数就是 $3$ 右边最大的数。如果 $3$ 右侧相邻数小于 $3$ ，那么 $3$ 右边必然没有大于 $3$ 的数。因此，这一步可以简化为，从右到左，找第一个小于右侧相邻数的数 $x$ 。
找 $3$ 右边最小的大于 $3$ 的数。由于 $3$ 右边的数是递减的，所以再遍历一遍，从右到左找第一个大于 $3$ 的数，就是 $3$ 右边最小的大于 $3$ 的数。我们找到的数是 $4$ 。然后把 $4$ 放到 $3$ 的位置上，把 $3$ 放到右边的三个位置中。这一步可以简化为交换 $3$ 和 $4$ 。交换后得到 $[1, 4, 5, 3, 2]$ 。注意交换后 $5, 4, 2$ 变成 $5, 3, 2$ ，仍然是递减的（证明见答疑）。
把 $4$ 右边的数从小到大排序。由于第二步交换后， $4$ 右边的数 $5, 3, 2$ 是递减的，所以只需把 $5, 3, 2$ 反转，就得到了答案 $[1, 4, 2, 3, 5]$ 。

算法

把上述过程一般化，同时对比「下一个整数」的算法：

下一个排列	下一个整数	相同点
从右到左，找第一个小于右侧相邻数的数 $x$	从右到左，找第一个小于 $9$ 的数字 $x$	都是找第一个小于右侧相邻数的数
找 $x$ 右边最小的大于 $x$ 的数 $y$ ，交换 $x$ 和 $y$	把 $x$ 加一，得到 $y = x + 1$	增大这个数
反转 $y$ 右边的数，把右边的数变成最小的排列	把 $y$ 右边的数字都变成 $0$	把右边的数变到最小

特别地，如果第一步没有找到这样的 $x$ ，说明 $nums$ 是递减的，是最后一个排列（字典序最大的排列）。此时跳过第二步，反转整个 $nums$ ，结果一定是递增的，即第一个排列（字典序最小的排列）。

答疑

问：第一步找到 $x$ 后，为什么 $x$ 右边的数是递减的？

答：反证法。假设 $x$ 右边的数不是递减的，也就是说，在 $x$ 的右边，存在 $nums [i] < nums [i + 1]$ 的情况，那么我们应把 $nums [i]$ 当作 $x$ ，这与事实矛盾。

问：为什么第二步交换后，右边的序列仍然是递减的？

答：设交换前 $nums = [\dots, x, c, b, a, \dots]$ ，其中大小关系为 $c > b > x > a$ 。那么 $x$ 右边最小的大于 $x$ 的数是 $b$ 。交换 $x$ 和 $b$ ，得到 $[\dots, b, c, x, a, \dots]$ ，其中 $c > x > a > \dots$ ，仍然是递减的。

问：如果 $nums$ 是第一个排列，我们是怎么算的？

答：例如 $nums = [1, 2, 3]$ 。第一步找到 $2$ ，第二步交换 $2$ 和 $3$ ，第三步反转 $2$ （只有一个数，反转后还是 $2$ ），最终得到 $[1, 3, 2]$ 。读者可以动手算算 $[1, 3, 2]$ 的后续排列，以加深印象。

Python 解法1C++ 解法1

python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)

        # 第一步：从右到左找到第一个小于 nums[i+1] 的数 nums[i]
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        # 如果找到了，进入第二步；否则跳过第二步，反转整个数组
        if i >= 0:
            # 第二步：从右到左找到 nums[i] 右边最小的大于 nums[i] 的数 nums[j]
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            # 交换 nums[i] 和 nums[j]
            nums[i], nums[j] = nums[j], nums[i]

        # 第三步：反转 nums[i+1:]（如果上面跳过第二步，此时 i = -1）
        # nums[i+1:] = nums[i+1:][::-1] 这样写也可以，但空间复杂度不是 O(1) 的
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();

        // 第一步：从右到左找到第一个小于 nums[i+1] 的数 nums[i]
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 如果找到了，进入第二步；否则跳过第二步，反转整个数组
        if (i >= 0) {
            // 第二步：从右到左找到 nums[i] 右边最小的大于 nums[i] 的数 nums[j]
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // 交换 nums[i] 和 nums[j]
            swap(nums[i], nums[j]);
        }

        // 第三步：反转 [i+1, n-1]（如果上面跳过第二步，此时 i = -1）
        reverse(nums.begin() + i + 1, nums.end());
    }
};

C++ 解法3

cpp

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        ranges::next_permutation(nums);
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。最坏情况下需要遍历整个 $nums$ 数组。
空间复杂度： $O (1)$ 。

变形题

改成求「上一个排列」，怎么做？

欢迎在评论区分享你的思路/代码。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

引入 ​

例子 ​

算法 ​

答疑 ​

复杂度分析 ​

变形题 ​

相关问题 ​

分类题单 ​

引入

例子

算法

答疑

复杂度分析

变形题

相关问题

分类题单