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
class Solution {
public String getPermutation(int n, int k) {
if (n <= 0 || k <= 0) {
return "";
}
StringBuilder res = new StringBuilder();
StringBuilder nums = new StringBuilder();
for (int i = 1; i <= n; i++) {
nums.append(i);
}
--k;
int[] factorial = new int[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
}
for (int i = 1; i <= n; i++) {
int index = k / factorial[n - i];
res.append(nums.charAt(index));
nums.deleteCharAt(index);
k -= index * factorial[n - i];
}
return res.toString();
}
}

3. Time & Space Complexity

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