Difficulty: Medium
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.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Language: Java
class Solution {
public String getPermutation(int n, int k) {
int[] factorial = new int[n + 1];
List<Integer> leftNumList = new ArrayList<>();
int sum = 1;
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
leftNumList.add(i);
sum *= i;
factorial[i] = sum;
}
StringBuilder stringBuilder = new StringBuilder();
k--; // Amazing k--
for (int i = 1; i <= n; i++) {
int index = k / factorial[n - i];
k = k % factorial[n - i];
stringBuilder.append(leftNumList.get(index));
leftNumList.remove(index);
}
return stringBuilder.toString();
}
}