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 <= 1000 <= 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 同款。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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:后缀变成最小排列
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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()));