leetcode 60 第k个排列 康托展开

缘起

继续全排列之旅!!! leetcode 60 第k个排列

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。
示例 1:

输入: n = 3, k = 3
输出: "213"
示例 2:

输入: n = 4, k = 9
输出: "2314"

【1】中已经给出了康托展开的思路. 所以本题的算法是显然的. 就是将k进行康托展开.

没写注释, 详见 【1】

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
	string getPermutation(int n, int k) {
		return rcantor(fac(n),k, n);
	}

private:
	int fac(int n) // 计算 n!
	{
		int ans =1;
		for (int i = 1; i<=n; i++)
		{
			ans*=i;
		}
		return ans;
	}

	string rcantor(int f, int k, int n)
	{
		string ans;
		vector<int> p(n+1), x(n+1);
		vector<bool> v(n+1);
		k--;
		for (int i = n;i; i--)
		{
			f/=i;
			x[n-i+1] = k/f;
			k%=f;
		}
		for (int i = 1; i<=n; i++)
		{
			p[i] = x[i]+1;
			for (int j = 1; j<=p[i]; j++)
			{
				if (v[j])
				{
					p[i]++;
				}
			} 
			v[p[i]] = true; 
		}
		for (int i = 1; i<=n; i++)
		{
			ans.push_back('0'+p[i]);
		}
		return ans;
	}
};

参考

【1】https://yfsyfs.github.io/2019/09/13/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80%E6%B1%82%E5%85%A8%E6%8E%92%E5%88%97/