31. 下一个排列

题目描述

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

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

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

解题思路

本题并不需要我们给出数组元素按字典序排列的所有排列组合结果（排列组合问题，一般用回溯法），而只要求在所有排列组合结果中，当前排列顺序的下一个排列。因此，本题的分析面就从所有的排列缩小到当前排列与下一个排列之间的关系。解题目标就是设计贪心策略来将当前排列转换为下一个排列。

简单的策略设计题不太适合引入复杂的数论证明，直接经验判断+举例子的方式能更快地归纳出方法。

如果我们想让当前排列更大，那么就应该把排列中的较小数往后挪，把排列中的较大数往前挪。例如，如果要让 [1, 2, 3] 更大，就应该把 2 或者 3 往前挪，而把 1 往后挪。

如果我们想让更大的排列尽可能地小，那么较小数的数位越低越好。例如，把 [1, 2, 3] 中的 2 往后挪要比 1 往后挪更好，因为数字2的数位更低。较小数左侧的高位部分应该保持不变。

如果我们已经找到了一个合适的较小数，并且已经把较小数往后挪了：

  • 那么我们只要保证原较小数的位置上的新元素比我们找到的较小数要大，那么新的排列就一定比原来的排列要大
    • 例如，[1, 2, 3, 4, 5, 6, 7] 中，把 3 替换成 4 后，保持 [1, 2] 不变，那么所得的排列一定比 [1, 2, 3, …] 要大
  • 为了使新排列的高位部分尽可能地小，原较小数的位置上的新元素应该越小越好
    • 例如，[1, 2, 3, 4, 5, 6, 7] 中，把 3 替换成 4 要比 5、6、7更好，因为 4 最小
    • 在之后的分析中，我们把这个用来替换的新元素称为较大数。
  • 为了使新排列的低位部分尽可能地小，原较小数右侧的元素应该从小到大排序
    • 例如，[1, 2, 3, 4, 7, 6, 5] 中，把 3 替换成 4 之后，低位部分的 [3, 7, 6, 5] 要从小到大排序成 [3, 5, 6, 7]

归纳以上的贪心策略，可以得出以下的算法原型：

  • 从右往左逆序遍历数组，找到满足条件 nums[i] < nums[i+1] 的元素 nums[i] ，来作为较小数
    • 如果没有找到较小数，说明数组已经按逆序排列，此时按题目要求，将数组反转后返回
  • 找到较小数 nums[i] 后，我们可以保证 nums[i+1, i+2, ...] 上的元素是逆序排列的
    • 再一次从右往左遍历数组，在较小数的右侧找一个刚刚好比它大的较大数
    • 将较小数和较大数交换顺序
  • 重新按从小到大顺序排列较小数右侧的低位部分、
    • 重排并不需要 sort ，我们已经知道低位部分是逆序了，所以只需要反转低位部分数组即可

复杂度分析

时间复杂度：扫描和反转的复杂度都是 O(N)
空间复杂度：算法就地完成，复杂度O(1)

知识点

排列组合、排序、贪心

代码

  1. class Solution {
  2. public:
  3.     void nextPermutation(vector<int>& nums) {
  4.         if (nums.empty()) {
  5.             return;
  6.         }
  8.         int n = nums.size();
  10.         // Find the right-most smaller element
  11.         int smallerElementIndex = n - 2;
  12.         while (smallerElementIndex >= 0) {
  13.             if (nums[smallerElementIndex] < nums[smallerElementIndex + 1]) {
  14.                 break;
  15.             }
  16.             --smallerElementIndex;
  17.         }
  19.         // Already get the greatest permutation
  20.         if (smallerElementIndex < 0) {
  21.             reverse(nums.begin(), nums.end());
  22.             return;
  23.         }
  25.         // Find the greater element on the right side of the smaller element
  26.         int greaterElementIndex = n - 1;
  27.         while (greaterElementIndex > smallerElementIndex) {
  28.             if (nums[smallerElementIndex] < nums[greaterElementIndex]) {
  29.                 break;
  30.             }
  31.             --greaterElementIndex;
  32.         }
  34.         swap(nums[smallerElementIndex], nums[greaterElementIndex]);
  36.         // Re-sort the right side of the vector
  37.         reverse(nums.begin() + smallerElementIndex + 1, nums.end());
  39.         return;
  40.     }
  41. };

参考资料

  1. Leetcode官方题解
  2. cppreference algorithm reverse()