leetcode 46 全排列 康托展开

缘起

开启全排列leetcode 四连弹之旅！！！ leetcode 46 全排列

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

【1】中已经给出了 dfs解法. 这里就不再使用这种解法了. 而是使用康托展开. 康托展开的原理在【2】中已经说明白了. 代码没有给注释, 详细注释见 【2】

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
49
50
51
52
53
54
55
56
57
class Solution {
public:
	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> ans;
		n = nums.size();
		f = fac();
		int t = f;
		for (int a = 1; a<=t; a++)
		{
			vector<int> p(n),x(n+1); // x和p初始化容量
			vector<bool> v(n+1);
			rcantor(a, p, x, v);
			for (int i = 0; i<n; i++)
			{
				p[i] = nums[p[i]-1];
			}
			ans.push_back(p);
			f =t;
		}
		return ans;
	}

private:
	int n,f;
	void rcantor(int a, vector<int> &p, vector<int> &x, vector<bool> &v)
	{
		a--;
		for (int i = n;i; i--)
		{
			f/=i;
			x[n-i+1] = a/f;
			a%=f;
		}
		for (int i = 1; i<=n; i++)
		{
			p[i-1] = x[i]+1;
			for (int j = 1; j<=p[i-1]; j++) 
			{
				if (v[j]) 
				{
					p[i-1]++;
				}
			}
			v[p[i-1]] = true; 
		}
	}

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

ac情况 （有点水~）

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

参考

【1】https://yfsyfs.github.io/2019/05/27/%E5%85%A8%E6%8E%92%E5%88%97/

【2】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/