題目鏈接
https://leetcode.com/problems/permutation-sequence/
解題思路
n個(gè)數(shù)要求第k個(gè)排列虽惭，可以先根據(jù)k在n個(gè)數(shù)里面先確定第一個(gè)數(shù)并更新k，之后問(wèn)題就變成了在剩下的n-1數(shù)里面找更新后的第k個(gè)排列的子問(wèn)題蛾茉。
代碼
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> fac(n + 1, 0);
vector<int> nums(n);
//fac[i]表示i的階乘 num[i]是i+1
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i;
nums[i - 1] = i;
}
string ans;
while (!nums.empty()) {
//在nums數(shù)組里確定取哪個(gè)數(shù)
int &t = fac[nums.size() - 1];
//i表示取的nums數(shù)組里的第幾個(gè)數(shù)葛虐，從1開(kāi)始
int i = k / t;
if (k % t != 0 || i == 0) {
i++;
}
//更新k
k = k - (i - 1) * t;
ans.push_back((char) (nums[i - 1] + '0'));
nums.erase(nums.begin() + i - 1);
}
return ans;
}
};
