关于vector的初始化
vector<vector<int> > ans(n, vector<int> n(n, 0));初始化二维的vector，大小为[n][n]，0填充，否则不能直接用ans[i][j]
60. 第k个排列
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
1
2
3
4
5
6
| "123"
"132"
"213"
"231"
"312"
"321"
|
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
1
2
| 输入: n = 3, k = 3
输出: "213"
|
示例 2:
1
2
| 输入: n = 4, k = 9
输出: "2314"
|
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
| #include <bits/stdc++.h>
using namespace std;
int fac(int n) {
int ans = 1;
for(int i = 2;i <= n;i++) {
ans *= i;
}
return ans;
}
int getPermutation(int n, int k) {
set<int> usedSet;
int result = k - 1;
int remain = 0, iFac = 0;
int ans = 0;
for(int i = 1;i <= n;i++) {
iFac = fac(n - i);
remain = result % iFac;
result /= iFac;
int iLoop = 0, temp = 0;
for(int j = 1;j <= n;j++) {
if(usedSet.find(j) == usedSet.end()) {
iLoop++;
}
if(iLoop == result + 1) {
usedSet.insert(j);
ans += j * pow(10, n - i);
break;
}
}
result = remain;
}
return ans;
}
int main() {
cout << getPermutation(5, 40);
}
|
解释：这里不能采用回溯的方法一个一个的求，否则会超时
其实如果是求第k个排列，根本就不需要从头开始一个一个地求解。
如果需要求n=5的第40个排列
首先_ _ _ _ _五个位置中先确定高位
如何确定？剩下四位数全排列总共有4! = 24种情况
40 / 24 = 1，也就是说在首位可以有一种全排列，剩余一种不完整。
所以首位为1，剩余40 - 24 = 16中情况在余下4位中解决
3! = 6， 16 / 6 = 2，所以余下的三位数中有两种全排列，还有一种不完整，除去2已经用过了，剩下的从小到大的第2位数（从0开始数）就是4，所以现在已经确定2 4 _ _ _，余下也一样
——康托展开