原题描述
+
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
原题链接:https://leetcode-cn.com/problems/next-permutation
思路解析
+
得研究一下数字上的规律,用实例可能更容易说清楚。
举例这个数字158476531,我们在下图中,把它分为两部分。红色指定的是尾部降序的部分。应该清楚的意识到,当一组数字处于降序排列时,它就是这些数字能组成的最大值了。
所以,通过只交换动红色部分的数字来期待获取更大的值,是根本不可能做到的。这就必须要开始让蓝色部分的数字参与了。
为此,我们向前再多看一位数字。如下图所示,这时的数字不是降序,它是有潜力通过内部交换而得到下一个排列的。
现在的问题是,内部怎么交换。数字4这个位置肯定是要被换掉的,为了并且交换之后,新的数字必须是下一个排列,不能是下下个排列。所以我们应该让这个数字不要太大,只比当前的数字大即可。
如果4与7或者6交换,很明显是大了太多了;与3或1交换,又会比当前的小。那么选择的依据就是将将比4大的数字,那就是5。
还没结束,交换之后,后面的数字要改成升序,变成最小值才行。
复杂度分析
+
C++参考代码
+
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if (nums.size() < 2) return;
int n = nums.size();
int i = n - 2, j = n - 1, k = n - 1;
while (i >= 0 && nums[i] >= nums[j]) {
--i; --j;
}
if (i >= 0) {
while (k >= j && nums[k] <= nums[i]) --k;
swap(nums[k], nums[i]);
}
reverse(nums.begin() + j, nums.end());
}
};