Description#
The set [1, 2, 3, ..., n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123""132""213""231""312""321"
Given n and k, return the kth permutation sequence.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Example 3:
Input: n = 3, k = 1
Output: "123"
Constraints:
Solutions#
Solution 1: Enumeration#
We know that the set $[1,2,..n]$ has a total of $n!$ permutations. If we determine the first digit, the number of permutations that the remaining digits can form is $(n-1)!$.
Therefore, we enumerate each digit $i$. If $k$ is greater than the number of permutations after the current position is determined, then we can directly subtract this number; otherwise, it means that we have found the number at the current position.
For each digit $i$, where $0 \leq i < n$, the number of permutations that the remaining digits can form is $(n-i-1)!$, which we denote as $fact$. The numbers used in the process are recorded in vis.
The time complexity is $O(n^2)$, and the space complexity is $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();
}
}
|
