思路
- 因为找的是字典序升序的下一个排列,因此要尽量保证前面不动,我们从后往前考虑
- 从后往前找到第一个非降序的位置,然后把这个位置的数字和最小的比它大的数字交换,最后从该位置后整理为升序
- 从数组末尾往前找,找到
第一个
位置 j
,使得 nums[j] < nums[j + 1]
。
- 如果不存在这样的
j
,则说明数组是不递增的,直接将数组逆转即可。
- 如果存在这样的
j
,则从末尾找到第一个位置 i > j
,使得 nums[i] > nums[j]
。
- 交换
nums[i]
与 nums[j]
,然后将数组从 j + 1
到末尾部分逆转。
时间复杂度分析
实现代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n=nums.size()-1;
while(n&&nums[n]<=nums[n-1]) n--;
if(n<=0) reverse(nums.begin(),nums.end());//整体降序
else
{
//此时nums[n]>nums[n-1]
int t=n;
while(t<nums.size()&&nums[t]>nums[n-1])//寻找最小的且>nums[n-1]的数
t++;
swap(nums[t-1],nums[n-1]);
reverse(nums.begin()+n,nums.end());//将k后面的数改成升序
}
return;
}
};