leetcode 31 下一个排列

缘起

继续全排列之旅!!! leetcode 31 下一个排列

分析

1
2
3
4
5
6
7
8
9
10
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

如果数字是不重复的话，则思想在 【1】中已经详细说过了. 题目中说的 必须原地修改，只允许使用额外常数空间。 其实就是为了防止你遍历全排列. 其实这样会被T掉的. 本题的算法显然是先进行康托展开求原全排列的哈希值，然后使用逆康托展开下一个哈希值. 但是遗憾的事情是，本题参与全排列的数字是可能重复的. 就不能这么干.

怎么做呢? 看下面的图

从全排列的末尾an倒序一直保持非降的趋势. 即ak>=ai>=aj>=an

但是现在来了个 a_{k-1} 它严格<ak 导致破坏了非降的趋势. 假设aj<=a_{k-1}<ai, 即找到非降序列中第一个严格大于a_{k-1}的数——ai, 然后将ai和a_{k-1}交换. 变成

再将ak->…->an逆序就是下一个全排列.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
	void nextPermutation(vector<int>& nums) {
		int n = nums.size();
		vector<int> kk;
		kk.push_back(nums[n-1]);
		nums.pop_back();
		while(!nums.empty() && nums.back()>=kk.back())
		{
			int t = nums.back();
			nums.pop_back();
			kk.push_back(t);
		} // 则 kk中已经是非降排序的, 所以不需要逆序了
		if (nums.empty()) // 说明原先是逆序, 则只需要输出kk即可(kk已成顺序)
		{
			nums = kk;
		}
		else // 说明nums的最后一个元素<kk的最后一个元素
		{
			vector<int>::iterator x = upper_bound(kk.begin(), kk.end(), nums.back()); // 找到kk中第一个严格>nums最后一个元素的元素x
			swap(nums.back(), *x); // 交换二者
			for (vector<int>::iterator vit = kk.begin(); vit!=kk.end(); vit++)
			{
				nums.push_back(*vit);
			}
		}
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
12 ms
, 在所有 C++ 提交中击败了
83.44%
的用户
内存消耗 :
8.7 MB
, 在所有 C++ 提交中击败了
81.72%
的用户

这里已经无力吐槽 leetcode的输入输出~ 和各大OJ太不一样~ QAQ

参考

【1】https://yfsyfs.github.io/2019/09/13/康托展开求全排列/