60. Permutation Sequence
Tags: ‘Math’, ‘Backtracking’
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"
Solution
方法1： 暴力，next permutation 执行k次， $O(nk) O()$
方法2：“康托算法” leetcode 解释
注意 k = k-1 来处理 $k\%(n-1)! = 0$ 的情况
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
List<Integer> nums = new ArrayList<>(); // for number loop up
int factorial = 1;
for (int i = 1; i <=n; i++) {
factorial = factorial * i;
nums.add(i);
}
k = k-1; // starting index of 0
for (int i = 0; i < n; i++) {
factorial = factorial/(n - i); // current grouping size
int index = k / factorial; // k / factorial
sb.append(nums.remove(index)); // remove and append to sb
k = k - index * factorial; // residual, which is k % factorial
}
return sb.toString();
}