假设集合像[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:= k mod事实[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