Giả sử tập hợp [1,2,3,...,n] chứa tổng cộng n! hoán vị duy nhất. Liệt kê và gán nhãn tất cả các hoán vị theo thứ tự, ta có chuỗi cho n = 3: ["123","132","213","231","312","321"]. Cho n và k, trả về chuỗi hoán vị thứ k. n từ 1 đến 9, k từ 1 đến n!. Ví dụ n = 3.
Các bước:
- ans := chuỗi rỗng, mảng candidates kích thước n
- for i in range 0 to n – 1
- candidates[i] := ((i + 1) + ký tự '0')
- Tạo mảng fact kích thước n + 1, fact[0] := 1
- for i in range 1 to n
- fact[i] := fact[i – 1] * i
- giảm k 1
- for i := n – 1 down to 0
- idx := k / fact[i]
- ans := ans + candidates[idx]
- for j := idx, j + 1 < kích thước candidates
- candidates[j] := candidates[j + 1]
- k := k mod fact[i]
- return ans
Hãy xem triển khai sau:
Ví dụ
#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); }Input
4 9
Output
2314