题目描述
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
样例
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路
以三位数字为例,123的下一个较大的排列是132,132下一个较大的排列是213,
不难发现,下一个较大的排列是从后向前遍历中较大的数与较小的数互换位置,然后较小的数后面的数翻转
通过两次遍历查找较大的数和较小的数
第一次从后向前遍历,如果是升序就继续查找,直到找到第一个不是升序的数,记录该数的下标
第二次从后向前遍历,找到第一个大于上面的数的数,两数进行交换,然后对后面的数字进行翻转即可。
如果上面的都没有找到说明该排列已经是降序排列(即已经是最大的排列),这时只需要将排列翻转即可。
C++ 代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
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 --;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};