Question
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 (ie, 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.
Solution -- Math
We can conclude a pattern by obeservation.
[x1, x2, x3, .., xn]
If we fix x1, then number of permutations is (n - 1)!
If we fix x1 and x2, then number of permutations is (n - 2)!
Following this thinking way, we can solve this problem by finding xi iteratively.
We also need a visited array here to note which element has been used.
public class Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder(n);
if (n < 1 || n > 9)
return sb.toString();
int factorial = 1;
for (int i = 1; i <= n; i++) {
factorial *= i;
}
if (k > factorial || k < 1)
return sb.toString();
boolean[] visited = new boolean[n];
int num = n;
int start = 1;
while (num > 0) {
factorial /= num;
start += (k / factorial);
if (k % factorial == 0)
start -= 1;
int index = 0;
for (int i = 1; i <= n; i++) {
// Find the right index
if (!visited[i - 1])
index++;
if (index == start) {
sb.append(i);
visited[i - 1] = true;
break;
}
}
k = k - (start - 1) * factorial;
start = 1;
num--;
}
return sb.toString();
}
}