一开始想用permutations那种全排列来计算，DFS写了好久发现人家n可以是9位数，递归几千万次这得什么计算机做得到。。
DFS(只能计算n很小的情况。。不可行)
String res = "";
public String getPermutation(int n, int k) {
int[] count = new int[1];
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = i + 1;
}
backtracking(count, k, num, "", new boolean[num.length]);
return res;
}
private void backtracking(int[] count, int k, int[] nums, String item, boolean[] used) {
if (item.length() == nums.length) {
if (++count[0] == k) {
res = item;
}
return;
}
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
used[i] = true;
backtracking(count, k, nums, item + nums[i], used);
used[i] = false;
}
}
}
数学方法：
每次计算最高位的数字，用一个数组保存剩下的数字。index代表剩下的数字的位置。
index计算的方法是：
index = k / (n-1)!
这个index就表示，之前有index组个全排列（开头是同一个数字的一组全排列算是一组）
k就减去之前index * (n-1)!那么多个排列，再循环计算新的index即可。
public String getPermutation(int n, int k) {
int[] factorial = new int[n];
factorial[0] = 1;
for (int i = 1; i < n; i++) {
//阶乘
factorial[i] = i * factorial[i - 1];
}
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
//k从0开始
k--;
StringBuilder res = new StringBuilder();
for (int i = 1; i <= n; i++) {
int index = k / factorial[n - i];
res.append(nums.remove(index));
k -= index * factorial[n - i];
}
return res.toString();
}
