資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會學
時裝設計
法律研究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 的陣列 candidates
- 對於從 0 到 n – 1 的 i
- candidates[i] := ((i + 1) + 字元 '0')
- 建立一個名為 fact 的大小為 n + 1 的陣列，設定 fact[0] := 1
- 對於從 1 到 n 的 i
- fact[i] := fact[i – 1] * i
- 將 k 減少 1
- 對於從 n – 1 到 0 的 i
- idx := k / fact[i]
- ans := ans + candidates[idx]
- 對於從 idx、idx + 1 到 candidates 大小的 j
- candidates[j] := candidates[j + 1]
- k := k mod fact[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
更新於:04-五月-2020
495 次瀏覽
廣告