给出集合[1,2,3,…,n]，其所有元素共有n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定n 和k，返回第k个排列。
说明：
给定 n的范围是 [1, 9]。
给定 k 的范围是[1,n!]。
大致思路是根据k与总排列数(n!)的关系来推断出第k个排列，而不用依次求出排列直到第k个。
以每个数字开头的排列都有(n-1)!个，k/(n-1)!即可以求出字符串index为n-k-1处的字符。（注意字符串的index并非n-k，需要在开头加k--），以此类推更新k为除以(n-1)!所得的余数，更新n为n-1，再求下一位，直到n为1时终结。
如果使用递归则思路简单但很容易超时，基本也就是尾递归，用循环代替即可。
参考：https://blog.csdn.net/xiaoliucool1314/article/details/50777335
代码(java)：
class Solution{
public string getPermutation(int n, int k){
k--;
List<Integer> nums = new ArrayList<>();
for(int i = 1;i <= n;i++)
nums.add(i);
int fac = 1;
for(int i = 2;i < n;i++)
fac *= i;
int count = n - 1;
StringBuilder res = new StringBuilder();
while(count >= 0){
res.append(nums.remove(k / fac));
k %= fac;
if(count > 0)
fac /= count;
count--;
}
return res.toString();
}
}
