HHot 100C++ 图解

31. 下一个排列

一句话套路找下降位→换「刚好更大」的→反转后缀

题目描述

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

  • 例如,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:

输入: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

思路

时间O(n)
空间O(1)

思路

思路(字典序 next_permutation 的实现):

  • 1) 从右往左找第一个 a[i] < a[i+1],称 i 为「变弱位」;找不到说明整体降序 -> 已是最大。
  • 2) 若存在 i,从右往左找第一个 a[j] > a[i](在降序后缀里等价于「刚好比 a[i] 大」),交换。
  • 3) 反转 i 之后的部分(它本来降序,反转后即升序 = 最小)。

直觉

把尽量靠右的低位抬高一点点,然后让后面尽可能小。

标准库

std::next_permutation 就是这套逻辑;Q556(四位数的下一个更大元素)、Q670 同款。

图解

1 0 2 1 3 2 4 3
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/17_tricks.cpp17 行
namespace lc0031 {
class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    const int n = (int)nums.size();
    if (n == 0) return;  // 空数组时 i = -2,下面 begin() + i + 1 会算出非法迭代器
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) --i;  // 步骤 1:找下降位
    if (i >= 0) {
      int j = n - 1;
      while (nums[j] <= nums[i]) --j;  // 步骤 2:右边降序段里第一个更大的
      swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());  // 步骤 3:后缀变成最小排列
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q31_next_permutation22 行
lc0031::Solution s;
auto next = [&](vector<int> v) {
  s.nextPermutation(v);
  return v;
};
CHECK_EQ(next({1, 2, 3}), vector<int>{1, 3, 2});
CHECK_EQ(next({3, 2, 1}), vector<int>{1, 2, 3});  // 降序 -> 回到最小
CHECK_EQ(next({1, 1, 5}), vector<int>{1, 5, 1});
CHECK_EQ(next({1, 3, 2}), vector<int>{2, 1, 3});
CHECK_EQ(next({2, 3, 1}), vector<int>{3, 1, 2});
CHECK_EQ(next({1}), vector<int>{1});
CHECK_EQ(next({5, 1, 1, 5}), vector<int>{5, 1, 5, 1});
CHECK_EQ(next({1, 2, 3, 4}), vector<int>{1, 2, 4, 3});
// 与标准库行为一致(对拍 4! 种排列)
vector<int> base{1, 2, 3, 4};
sort(base.begin(), base.end());
do {
  vector<int> mine = base, std_v = base;
  s.nextPermutation(mine);
  std::next_permutation(std_v.begin(), std_v.end());
  CHECK_EQ(mine, std_v);
} while (next_permutation(base.begin(), base.end()));

↑↓ 选择↵ 打开/ 随时唤起