Problem:
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 for n = 3:
1."123"
2."132"
3."213"
4."231"
5."312"
6."321"
Given n and k, return the (k^{th}) permutation sequence.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
思路：
以n=4,k=14为例。n=4时共有(n!=24)种排列。由于从0开始算，所以应该求第((k-1)=13)个数。实际上就是考虑固定某一位时后面的全排列总数。当第一位为1~4时，后面的3位共有(3!=6)种排列。很明显，首位大的数顺序在首位小的数后面。由(13/6=2)可知，此时的首位为3。然后将3移除，此时相当于找以3为首位的第(k = k \% 6 = 1)个数（同样是从0开始算起），按照确定首位的方法确定第二位。第二位后面共有(2!=2)种排列。由(1/2=0)可知第二位为1。后面两位也由同样的方法确定，最后的结果为3142。
Solution:
string getPermutation(int n, int k) {
string dict(n, '0');
iota(dict.begin(), dict.end(), '1'); //用1到n填充dict
/*定义在 numeric 头文件中的 iota() 函数模板会用连续的 T 类型值填充序列。前两个参数是定义序列的正向迭代器，第三个参数是初始的 T 值。
第三个指定的值会被保存到序列的第一个元素中。保存在第一个元素后的值是通过对前面的值运用自增运算符得到的。当然，这意味着 T 类型必须支持 operator++()。*/
vector<int> factorial(n, 1);
for (int i = 2; i < n; i++) {
factorial[i] = factorial[i-1] * i;
}
k--; //从0开始算起
string res(n, '0');
for (int i = 0; i < n; i++) {
int select = k / factorial[n-1-i];
k %= factorial[n-1-i];
res[i] = dict[select];
//dict.erase(next(dict.begin(), select)); 这种表达式的用法还不清楚，故选择下一种方式，但此种方式运行时间为0 ms。
dict.erase(dict.begin() + select);
}
return res;
}
性能：
Runtime: 4 ms Memory Usage: 8 MB
