第K个排列
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。示例 1:
输入: n = 3, k = 3
输出: "213"示例 2:
输入: n = 4, k = 9
输出: "2314"
题目分析
1. 我一开始想到的是全排列的函数的复用，我能找到全排列难道我找不到第k个排列？但我发现全排列那里并没有按序排列，因此不可复用..
2. 可以复用 下一个排列 的函数，毕竟一直找找到第K个就好，效率较低，没尝试。
3. 数学计算
全排列每个位置的每个数其实是有数学特征的。
比如对 1 2 3
3.1 首位情况： 肯定先是1在首位两次，然后是2首位2次，然后是3首位两次。
3.2 次位情况：除掉首位数字，剩下的数字在nums[]中，同样也是先nums[0]作为次位，出现 尾部排列次数 次，然后是nums[1]...依次类推。
综上：即我们知道每位的次数情况，比如 1 2 3中，我们要找第5个排列，因为首位1在前两个， 首位2 在3 4 个，因此 第5个排列必然是首位3。
再看次位，第5个排列，除去 1 2 首位的四个，我们要找的是3首位的第一个，依次类推即可。
即我们可以直接计算出每一位应该是什么数字。然后组成result即可。
4.细节
1.当前位 每个数字出现次数，由尾部的全排列次数决定，而全排列是n！，因此最好能预置个阶乘结果数组。
- k/fac[n-1] 向上取整得i，此时该位应该是 nums里的第i个数（下标i-1），同时对nums删除这个数。
- n==1 时，nums只剩一个数，直接连上并返回。
题解代码
class Solution {
public:
string getPermutation(int n, int k)
{
//题解数组
const vector<int> fac = {0,1,2,6,24,120,720,5040,40320,362880,3628800};
string result(n,'0');
string nums(n,'0');
for(int i=0;i<n;i++)
nums[i]='1'+i;
for(int i=0;n>0;i++)
{
int a;
int left=0;
if(n>=2) //计算每个首位有多少个排列,跳过这些排列
{
left=fac[n-1];
a=k/left;
if(k%left!=0)
a++;
result[i]=nums[a-1];
k-=(a-1)*left;
nums.erase(a-1,1);
n--;
}
else //只剩一个数,直接修改返回
{
result[i]=nums[0];
return result;
}
}
return result;
}
};
