C ++中的置换序列
假设集合像[1,2,3，...，n]，总共包含n个！独特的排列。通过按顺序列出并标记所有排列，我们得到n=3的这些序列：[“123”，“132”，“213”，“231”，“312”，“321”]因此，如果n和k给出，然后返回第k个排列序列。n将在1到9（含）之间，而k将在1到n之间！（包括的）。例如，如果n=3。
让我们看看步骤-
ans：=空字符串，定义大小为n的候选数组
对于i，范围为0至n–1
候选人[i]：=（（（i+1）+字符'0'）
创建一个称为大小为n+1的事实的数组，设置fact[0]：=1
对于我在1到n范围内
fact[i]：=fact[i–1]*i
将k减1
对于i：=n–1降至0
候选人[j]：=候选人[j+1]
idx：=k/事实[i]
答案：=答案+候选人[idx]
对于j：=idx，j+1<候选大小
k：=kmod事实[i]
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
string getPermutation(int n, int k) {
string ans = "";
vector <char> candidates(n);
for(lli i = 0; i < n; i++)
candidates[i] = ((i + 1) + '0');
vector <lli> fact(n + 1);
fact[0] = 1;
for(lli i = 1; i <= n; i++)
fact[i] = fact[i - 1] * i;
k--;
for(lli i = n - 1; i >= 0; i--){
lli idx = k / fact[i];
ans += candidates[idx];
for(lli j = idx; j + 1< candidates.size(); j++)
candidates[j] = candidates[j + 1];
k = k % fact[i];
}
return ans;
}
};
main(){
Solution ob;
cout << ob.getPermutation(4, 9);
}输入值
4 9
输出结果
2314