Type：medium
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:
"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.
Givenkwill be between 1 and n! inclusive.
Example 1:
Input:n = 3, k = 3Output:"213"
本题要求求出n个数字排列组合的第k个数，根据例子中我们可以看出来，当给定n时，选好第一个数字，可以将(n-1)！个数值当作一组，（因为他们的第一个数字相同），当选好第一个数字和第二个数字后，(n-2)!个数值可以当作一组（因为他们的第一、二个数字相同）。那么给定k时，第一次可以用k除以(n-1)！的商来判断结果的第一个数字，而k除以(n-1)！的余数则是它在分组后的小组中排列的位置。以此类推。
class Solution {
public:
string getPermutation(int n, int k) {
string res;
string num = "123456789";
vector<int> f(n, 1);
//f[i]记录i!的值
for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
--k;
for (int i = n; i >= 1; --i) {
int j = k / f[i - 1];
k %= f[i - 1];
res.push_back(num[j]);
num.erase(j, 1);
}
return res;
}
};
