60 Permutation Sequence
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.
"123" - 2.
"132" - 3.
"213" - 4.
"231" - 5.
"312" - 6.
"321"
Given n and k, return the kth permutation sequence.
(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();
}
}
Math: 时间复杂度O(n), 空间复杂度O(n)
Last modified 3yr ago