题目描述
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3
-> 1,3,2
3,2,1
-> 1,2,3
1,1,5
-> 1,5,1
算法
(找规律) $O(n)$
找下一个排列就是从后往前寻找第一个出现降的地方,把这个地方的数字与后边某个比它大的的数字交换,再把该位置之后整理为升序。
- 从数组末尾往前找,找到
第一个
位置j
,使得nums[j] < nums[j + 1]
。 - 如果不存在这样的
j
,则说明数组是不递增的,直接将数组逆转即可。 - 如果存在这样的
j
,则从末尾找到第一个位置i > j
,使得nums[i] > nums[j]
。 - 交换
nums[i]
与nums[j]
,然后将数组从j + 1
到末尾部分逆转。
时间复杂度
- 线性遍历数组常数次,时间复杂度为 $O(n)$。
空间复杂度
- 没有使用任何额外的数组空间,故空间复杂度为 $O(1)$。
C++ 代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int j = -1;
for (int i = n - 2; i >= 0; i--)
if (nums[i] < nums[i + 1]) {
j = i;
break;
}
if (j == -1)
reverse(nums.begin(), nums.end());
else {
for (int i = n - 1; i > j; i--)
if (nums[i] > nums[j]) {
swap(nums[i], nums[j]);
break;
}
reverse(nums.begin() + j + 1, nums.end());
}
}
};
否则从数组末尾往前找,找到 第一个 位置 j,使得 nums[j] < nums[j + 1]。
咋啥前提都没有就开始否则了。。
QAQ
历史遗留问题,已修正
做个笔记:
交换 nums[i] 与 nums[j],然后将数组从 j + 1 到末尾部分逆转。
因为交换后, j + 1 到末尾一定是有序(从小到大的)
最后的升序为什么可以用逆序替代?
这是显然的,替换过后,从 最低位 到 当前位 的排列是单调递增的,我们把它变成单调递减的是找到一个最小的排列,满足比当前排列大
我懂了,之前是没搞懂为何交换后最低位到当前位递增,很奇妙的规律!
字典序example:
123
132
213
231
312
321
这个题目乍一看,连题目都看不懂了