题目描述
实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
样例
输入:nums = [1,2,3]
输出:[1,3,2]
算法1
解释下为什么算法是对的。(重要,重要,重要)
题目要求找到下一个排列,就是要求我们对一个排列,找到从前往后递增的排列的拐点a的前一个数字b,再换成比它大的数c。
举个例子: 12354, 找到拐点5, 前一个数字3, 再从后面找到比3大的最小的数字4,交换一下3和4, 最后将后面的数字捋成升序。
(模拟) $O(n)$
1.首先逆序扫描一遍数组,找到降序的点(即:图中红色的点)
如图:
int k = nums.size();
while (k > 0 && nums[k - 1] >= nums[k]) k --;
循环结束k
的值表示红色的点a的下标。
2.再在后面(蓝色圈出来部分),逆序找一遍比红色节点(图中的a)的前一个节点(图中的b)大的节点c,两者交换。
int t = k;
while (t < nums.size() && nums[t] > nums[k - 1]) t ++;
swap(nums[t - 1], nums[k - 1]);
循环结束后t
的值是比b小的点,t - 1
就是c的下标。
3.最后将后面(蓝色圈出来部分)下降的折线 捋成上升的形状。
reverse(nums.begin() + k, nums.end());
时间复杂度
总共扫描三遍。 $O(n)$
C++ 代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k = nums.size() - 1;
while (k > 0 && nums[k - 1] >= nums[k]) k --;
if (k <= 0){
reverse(nums.begin(), nums.end());
}else{
int t = k;
while (t < nums.size() && nums[t] > nums[k - 1]) t ++;
swap(nums[t - 1], nums[k - 1]);
reverse(nums.begin() + k, nums.end());
}
}
};