Sign in Subscribe
算法

下一个排列

loser

• 8 min read
Share

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

例如，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]

给你一个整数数组 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

原地交换 + 反转后缀：

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

        while (i >= 0 && nums[i] >= nums[i + 1])
        {
            i--;
        }

        if (i >= 0)
        {
            int j = n - 1;

            while (nums[j] <= nums[i])
            {
                j--;
            }

            swap(nums[i], nums[j]);
        }

        reverse(nums.begin() + i + 1, nums.end());
    }
};

核心思想

这题要求的是“刚好比当前排列大一点”的那个排列。

如果只是想让排列变大，很简单，随便把前面的一个小数和后面的一个大数交换就行。

但题目要的是下一个排列，所以不能变大太多。

这题最关键的观察是：

要得到下一个字典序排列，应该尽量只改变靠右的位置，并让改变后的后缀尽可能小。

因此标准做法分三步：

  1. 从右往左找到第一个满足 nums[i] < nums[i + 1] 的位置 i
  2. 从右往左找到第一个大于 nums[i] 的位置 j，交换 nums[i] 和 nums[j]
  3. 反转 i + 1 到末尾的后缀，让后缀变成最小顺序

为什么从右往左找 nums[i] < nums[i + 1]

字典序比较时，越靠左的位置越重要。

所以为了得到“刚好更大”的排列，应该尽量保持左边不变，只在靠右的位置做最小改变。

从右往左找第一个：

nums[i] < nums[i + 1]

这个位置 i 就是可以让排列变大的最靠右位置。

它右边的部分满足：

nums[i + 1] >= nums[i + 2] >= ... >= nums[n - 1]

也就是说，右侧后缀是非递增的。

这个后缀本身已经是它能组成的最大字典序排列。

如果只调整这个后缀，不改变 nums[i]，就无法得到更大的排列。

所以必须把 nums[i] 换成右侧一个更大的数。

为什么要找右侧刚好更大的数

找到位置 i 后，要在右侧后缀中找一个数替换 nums[i]。

为了让整个排列变大，这个数必须满足：

nums[j] > nums[i]

但为了让变大的幅度尽量小，应该选择右侧所有大于 nums[i] 的数中最小的那个。

由于右侧后缀是非递增的，所以从右往左找到的第一个大于 nums[i] 的数，就是“刚好更大”的那个数。

代码是：

int j = n - 1;

while (nums[j] <= nums[i])
{
    j--;
}

然后交换：

swap(nums[i], nums[j]);

交换后，nums[i] 位置变大了，整个排列也就比原来更大。

为什么最后要反转后缀

交换完成后，i 左边保持不变，nums[i] 已经变成了一个更大的数。

为了得到“下一个”排列，后面的部分必须尽可能小。

右侧后缀在交换前是非递增的。

交换后，它仍然可以通过反转变成非递减顺序，也就是字典序最小的排列。

所以执行：

reverse(nums.begin() + i + 1, nums.end());

这样得到的就是在前缀刚刚变大的前提下，后缀最小的排列。

因此整个数组就是原数组的下一个排列。

如果不存在下一个更大排列

如果从右往左没有找到 nums[i] < nums[i + 1]，说明整个数组都是非递增的。

例如：

nums = [3,2,1]

这已经是所有排列中字典序最大的一个。

根据题意，如果不存在下一个更大排列，就要变成字典序最小的排列。

对于非递增数组，直接反转整个数组即可得到升序排列：

[1,2,3]

代码中当 i == -1 时，会执行：

reverse(nums.begin(), nums.end());

正好完成这个处理。

边界情况

如果数组长度为 1，例如：

nums = [1]

不存在其它排列。

代码中 i = -1，最后反转整个数组，数组仍然不变。

如果数组中有重复元素，例如：

nums = [1,1,5]

从右往左找到：

nums[1] = 1 < nums[2] = 5

交换后得到：

[1,5,1]

重复元素不影响算法，因为比较时使用的是严格大于：

nums[j] > nums[i]

这样才能保证排列真的变大。

正确性证明

我们证明：算法得到的数组正好是原数组的下一个排列。

结论 1：如果不存在 nums[i] < nums[i + 1]，原数组已经是最大排列

如果整个数组从左到右非递增：

nums[0] >= nums[1] >= ... >= nums[n - 1]

那么它就是这些元素能组成的最大字典序排列。

不存在任何一个更大的排列。

根据题意，此时应该返回最小排列。

算法反转整个数组，使其变成非递减顺序，正好是最小排列。

结论 2：找到的 i 是最靠右、可以让排列变大的位置

算法从右往左找到第一个满足：

nums[i] < nums[i + 1]

的位置。

因此 i 右侧的后缀是非递增的，已经是该后缀能形成的最大排列。

如果不改变 nums[i] 或更左边的位置，仅调整右侧后缀，不可能得到更大的排列。

所以想得到下一个更大排列，必须在位置 i 处做改变。

因为 i 是最靠右的这样的位置，所以它会让左侧前缀尽可能长地保持不变。

结论 3：从右侧选择的 nums[j] 是能替换 nums[i] 的最小更大元素

右侧后缀是非递增的。

从右往左找到的第一个满足：

nums[j] > nums[i]

的元素，就是右侧所有大于 nums[i] 的元素中最小的那个。

用它替换 nums[i]，可以让位置 i 增大，但增大的幅度最小。

所以这一步保证了新排列刚好超过原排列，而不会跳过更近的可能。

结论 4：反转后缀后，后缀是当前前缀下的最小排列

交换完成后，位置 i 已经变成了刚好更大的元素。

此时为了让整个排列尽可能小，i 之后的后缀必须按非递减顺序排列。

算法通过反转原本非递增的后缀，让它变成非递减顺序。

因此在当前前缀下，后缀已经是最小字典序。

得出结论

由结论 1 可知，没有更大排列时，算法正确返回最小排列。

由结论 2 可知，算法选择了最靠右的可增大位置。

由结论 3 可知，算法在该位置使用了最小的更大元素。

由结论 4 可知，算法让后缀变成当前前缀下的最小排列。

因此算法得到的数组正好是原数组的下一个排列。

举例理解

以：

nums = [1,2,3]

为例。

从右往左找第一个下降点：

2 < 3

所以 i = 1，nums[i] = 2。

从右往左找第一个大于 2 的数，是 3。

交换后：

[1,3,2]

后缀只有一个元素，不需要变化。

所以结果是 [1,3,2]。

再看：

nums = [2,3,1]

从右往左找：

  • 3 >= 1，继续向左
  • 2 < 3，所以 i = 0

右侧大于 2 的最小元素是 3。

交换后：

[3,2,1]

再反转后缀 [2,1]：

[3,1,2]

所以 [2,3,1] 的下一个排列是 [3,1,2]。

复杂度分析

算法最多进行三次线性操作：

  • 从右往左找位置 i
  • 从右往左找位置 j
  • 反转后缀

所以时间复杂度是：

O(n)

算法只使用常数个额外变量。

所以空间复杂度是：

`O(1)