Permutation Sequence
public static String getPermutation(int n, int k) {
if (n == 1) {
return "1";
}
//新建一个长度为n的数组每个数组元素就表第i个使用没有。
boolean[] visited = new boolean[n+1];
int[] dp = new int[n+1];
//dp数组存放阶乘。
dp[0] = 1;
for (int i = 1; i < n+1; i++) {
dp[i] = dp[i - 1] * i;
}
return perm(n, k, visited, dp);
}
public static String perm(int n, int k, boolean[] visited, int[] dp) {
if(n == 0){
return "";
}
int pos = 1;
int cut = dp[n - 1];
while (k > cut) {
k -= cut;
pos++;
}
String s = Integer.toString(getVisited(visited, pos));
return s += perm(n - 1, k, visited, dp);
}
public static int getVisited(boolean[] visited, int index) {
int o = 0;
for (int i = 0; i < visited.length; i++) {
if (!visited[i]) {
o++;
}
if (o == index) {
visited[i] = true;
return i + 1;
}
}
return 0;
}
