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.
给定一个数字n，求从1到n的第k个排列。
这道题可以用深度优先搜索，配合一个全局计数变量解决，但是当k较大时，时间复杂度会趋近于n的阶乘。
观察给出的例子，第一位数子每两种组合加1，如果是四个数组，就是每6种组合加1，第i位的变化频次和它后面数组的组合数有关，所以k除以组合数 就可以求出第一位的数字。从数字list中删除这个数字，更新k值，可以按此方法求后面的数字。
public String getPermutation(int n, int k) {
if (k <= 0 || n <= 0) {
return "";
}
StringBuilder buffer = new StringBuilder();
//n个数字的排列数
int[] cnts = new int[n + 1];
cnts[0] = 1;
for (int i = 1; i <= n; i++) {
cnts[i] = cnts[i-1] * i;
}
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
k--;
while (nums.size() > 0) {
int index = k / cnts[n - 1];
buffer.append(nums.get(index));
k -= index * cnts[n - 1];
nums.remove(index);
}
return buffer.toString();
}