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