BiruLyu
7/14/2017 - 11:21 PM

## 60. Permutation Sequence(#).java

``````public class Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
boolean[] used = new boolean[n + 1];
int fac = 1;
for (int i = 1; i <= n; i++)
fac *= i;
k--;
for (int i = 0; i < n; i++){
fac /= n - i;
int idx = k / fac;
for (int j = 1; j <= n; j++){
if (used[j]) continue;
if (idx == 0){
sb.append(j);
used[j] = true;
k = k % fac;
break;
} else
idx--;
}
}

return sb.toString();
}

}``````
``````public class Solution {
public String getPermutation(int n, int k) {
int pos = 0;
List<Integer> numbers = new ArrayList<>();
int[] factorial = new int[n+1];
StringBuilder sb = new StringBuilder();

// create an array of factorial lookup
int sum = 1;
factorial[0] = 1;
for(int i=1; i<=n; i++){
sum *= i;
factorial[i] = sum;
}
// factorial[] = {1, 1, 2, 6, 24, ... n!}

// create a list of numbers to get indices
for(int i=1; i<=n; i++){
}
// numbers = {1, 2, 3, 4}

k--;

for(int i = 1; i <= n; i++){
int index = k/factorial[n-i];
sb.append(numbers.get(index));
numbers.remove(index);
k-=index*factorial[n-i];
}

return sb.toString();
}
}``````