60 Permutation Sequence

1. Question

The set[1,2,3,…,n]contains a total ofn! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, forn= 3):
  1. 1.
    "123"
  2. 2.
    "132"
  3. 3.
    "213"
  4. 4.
    "231"
  5. 5.
    "312"
  6. 6.
    "321"
Given n and k, return the kth permutation sequence.

2. Implementation

(1) Math
1
class Solution {
2
public String getPermutation(int n, int k) {
3
if (n <= 0 || k <= 0) {
4
return "";
5
}
6
7
StringBuilder res = new StringBuilder();
8
StringBuilder nums = new StringBuilder();
9
10
for (int i = 1; i <= n; i++) {
11
nums.append(i);
12
}
13
14
--k;
15
int[] factorial = new int[n + 1];
16
factorial[0] = 1;
17
for (int i = 1; i <= n; i++) {
18
factorial[i] = factorial[i - 1] * i;
19
}
20
21
for (int i = 1; i <= n; i++) {
22
int index = k / factorial[n - i];
23
res.append(nums.charAt(index));
24
nums.deleteCharAt(index);
25
k -= index * factorial[n - i];
26
}
27
return res.toString();
28
}
29
}
Copied!

3. Time & Space Complexity

Math: 时间复杂度O(n), 空间复杂度O(n)