C++ 中的排列序列
c++server side programmingprogramming
假设集合为 [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 的数组 candidates
- i 的范围从 0 到 n – 1
- candidates[i] := ((i + 1) + 字符 ‘0’)
- 创建一个名为 fact 的数组，大小为 n + 1，并设置 fact[0] := 1
- for i in range 1 to n
- fact[i] := fact[i – 1] * i
- decrease k by 1
- for i := n – 1 down to 0
- idx := k / fact[i]
- ans := ans + candidates[idx]
- for j := idx, j + 1 < size of candidates
- candidates[j] := candidates[j + 1]
- k := k mod fact[i]
- return 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
