文章目录
1. 题目信息
1.1 题目描述
题目链接: 31. 下一个排列
实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
1.2 测试用例
示例 1:
输入:nums = [1,2,3]
输出:[1,3,2]
- 示例 2:
输入:nums = [3,2,1]
输出:[1,2,3]
- 示例 3:
输入:nums = [1,1,5]
输出:[1,5,1]
- 示例 4:
输入:nums = [5]
输出:[1]
- 示例 5:
输入:nums = [1,2,3,5,4,2,1]
输出:[1,2,4,1,2,3,5]
- 提示:
1 <= nums.length <= 100
0 <= nums[i] <= 100
2. 题目分析
2.1 手动实现next_permutation
分三步完成, 从右往左找出一个最小的可以交换的数字对进行交换, 使得序列变大一点点, 我们以
[1,2,3,5,4,2,1]
为例;
- 先逆序找到第一个可用于和后面的值交换的较小值, 即找到第一个不满足升序的值, 数组中的
3
就是我们要找的这个 第一个较小值, 假设 下标i
, 此处例子中值为 2; - 再逆序找到这个倒着看升序. 顺着看是降序的序列
[5,4,2,1]
中的值大于nums[i]
的第一个下标j
, 使nums[i] < nums[j]
, 然后交换这两个数字, 此处例子就是找到 比3略大的4, 然后交换, 得到新数组: [1, 2,4
, 5,3
, 2, 1]; - 对 排在
(i, end)
也就是[i+1, end)
中的数字进行降序排列, 即直接逆序一下即可;
2.2 标准库的参考实现
template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
if (first == last) return false;
BidirIt i = last;
if (first == --i) return false;
while (true) {
BidirIt i1, i2;
i1 = i;
if (*--i < *i1) {
i2 = last;
while (!(*i < *--i2))
;
std::iter_swap(i, i2);
std::reverse(i1, last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}
3. 代码详情
3.1 C++
3.1.1 手动实现next_permutation
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if (next_permutation(nums.begin(), nums.end())) {
return;
}
// 如果返回false, 说明已经达到最大的排列, 并且已经进行了逆转成最小序列;
// cout << nums[0] << endl;
}
void nextPermutation_v1(vector<int>& nums) {
// 执行用时:4 ms, 在所有 C++ 提交中击败了80.53%的用户
// 内存消耗:11.8 MB, 在所有 C++ 提交中击败了49.02%的用户
int i = nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i+1]) {
i--;
}
// 找到从后往前的第一个下降值, 再次从后往前找到可以和这个值交换的第一个大于该下降值的值;
if (i >= 0) {
int j = nums.size() - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
// 一定可以找到这个合法的j;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};
3.2 Python
- 略