Keshawn_lu's Blog

Leetcode 60. 第k个排列

字数统计: 428阅读时长: 2 min
2020/09/05 Share

题目简介:

给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

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

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

给定 nk,返回第 k 个排列。

说明:

  • 给定 n 的范围是 [1, 9]。
  • 给定 k 的范围是[1, n!]。

示例 1:

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

示例 2:

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

思路:

深搜+回溯,需要注意的是需要剪枝,不然会超时。

我们先事先定义一个数组dpdp[n]代表n个数字所能构成的排列数。

当给定的k > dp[n - count - 1]时(count为当前已选择的数字个数),说明可以跳过该数字,直接进入下一个数字(减少时间)。

并且在回溯的时候可以放弃回溯,直接return,因为找的是第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
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
class Solution {
public:

vector<int> dp = vector<int>(10, 0);
string res;
vector<bool> used = vector<bool>(10, false);

void dfs(int n, int& k, int count, string& s){

if(count == n){

k--;
if(k == 0){

res = s;
return;
}
}

for(int i = 1; i <= n; i++){

if(used[i]) //之前已经用过了
continue;

if(dp[n - count - 1] < k){

k = k - dp[n - count - 1]; //减少计算
continue;
}

s += (i + '0');
used[i] = true;
dfs(n, k, count + 1, s);

return; //没必要尝试后面的了,快了很多
}
}

string getPermutation(int n, int k) {

dp[0] = 1;
dp[1] = 1;

for(int i = 2; i <= n; i++){

dp[i] = dp[i - 1] * i;
}

string s = "";
dfs(n, k, 0, s);

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: