题目描述
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3
输出："213"
示例 2：
输入：n = 4, k = 9
输出："2314"
示例 3：
输入：n = 3, k = 1
输出："123"
提示：
解法
方法一：枚举
我们知道，集合 \([1,2,..n]\) 一共有 \(n!\) 种排列，如果我们确定首位，那剩余位能组成的排列数量为 \((n-1)!\)。
因此，我们枚举每一位 \(i\)，如果此时 \(k\) 大于当前位置确定后的排列数量，那么我们可以直接减去这个数量；否则，说明我们找到了当前位置的数。
对于每一位 \(i\)，其中 \(0 \leq i \lt n\)，剩余位能组成的排列数量为 \((n-i-1)!\)，我们记为 \(fact\)。过程中已使用的数记录在 vis 中。
时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def getPermutation(self, n: int, k: int) -> str:
ans = []
vis = [False] * (n + 1)
for i in range(n):
fact = 1
for j in range(1, n - i):
fact *= j
for j in range(1, n + 1):
if not vis[j]:
if k > fact:
k -= fact
else:
ans.append(str(j))
vis[j] = True
break
return ''.join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public String getPermutation(int n, int k) {
StringBuilder ans = new StringBuilder();
boolean[] vis = new boolean[n + 1];
for (int i = 0; i < n; ++i) {
int fact = 1;
for (int j = 1; j < n - i; ++j) {
fact *= j;
}
for (int j = 1; j <= n; ++j) {
if (!vis[j]) {
if (k > fact) {
k -= fact;
} else {
ans.append(j);
vis[j] = true;
break;
}
}
}
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
string getPermutation(int n, int k) {
string ans;
bitset<10> vis;
for (int i = 0; i < n; ++i) {
int fact = 1;
for (int j = 1; j < n - i; ++j) fact *= j;
for (int j = 1; j <= n; ++j) {
if (vis[j]) continue;
if (k > fact)
k -= fact;
else {
ans += to_string(j);
vis[j] = 1;
break;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | func getPermutation(n int, k int) string {
ans := make([]byte, n)
vis := make([]bool, n+1)
for i := 0; i < n; i++ {
fact := 1
for j := 1; j < n-i; j++ {
fact *= j
}
for j := 1; j <= n; j++ {
if !vis[j] {
if k > fact {
k -= fact
} else {
ans[i] = byte('0' + j)
vis[j] = true
break
}
}
}
}
return string(ans)
}
|
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 | impl Solution {
pub fn get_permutation(n: i32, k: i32) -> String {
let mut k = k;
let mut ans = String::new();
let mut fact = vec![1; n as usize];
for i in 1..n as usize {
fact[i] = fact[i - 1] * (i as i32);
}
let mut vis = vec![false; n as usize + 1];
for i in 0..n as usize {
let cnt = fact[(n as usize) - i - 1];
for j in 1..=n {
if vis[j as usize] {
continue;
}
if k > cnt {
k -= cnt;
} else {
ans.push_str(&j.to_string());
vis[j as usize] = true;
break;
}
}
}
ans
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | public class Solution {
public string GetPermutation(int n, int k) {
var ans = new StringBuilder();
int vis = 0;
for (int i = 0; i < n; ++i) {
int fact = 1;
for (int j = 1; j < n - i; ++j) {
fact *= j;
}
for (int j = 1; j <= n; ++j) {
if (((vis >> j) & 1) == 0) {
if (k > fact) {
k -= fact;
} else {
ans.Append(j);
vis |= 1 << j;
break;
}
}
}
}
return ans.ToString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | function getPermutation(n: number, k: number): string {
let ans = '';
const vis = Array.from({ length: n + 1 }, () => false);
for (let i = 0; i < n; i++) {
let fact = 1;
for (let j = 1; j < n - i; j++) {
fact *= j;
}
for (let j = 1; j <= n; j++) {
if (!vis[j]) {
if (k > fact) {
k -= fact;
} else {
ans += j;
vis[j] = true;
break;
}
}
}
}
return ans;
}
|