Giả sử tập giống như [1,2,3, ..., n], chứa tổng n! các hoán vị duy nhất. Bằng cách liệt kê và gắn nhãn tất cả các hoán vị theo thứ tự, chúng ta nhận được dãy này cho n =3:["123", "132", "213", "231", "312", "321"] Vì vậy, nếu n và k được cho trước, sau đó trả về chuỗi hoán vị thứ k. N sẽ nằm trong khoảng từ 1 đến 9 (bao gồm) và k sẽ nằm trong khoảng từ 1 đến n! (bao gồm). Ví dụ nếu n =3.
Hãy để chúng tôi xem các bước -
- ans:=chuỗi rỗng, xác định mảng được gọi là ứng viên có kích thước n
- cho tôi trong phạm vi từ 0 đến n - 1
- ứng viên [i]:=((i + 1) + ký tự ‘0’)
- tạo một mảng được gọi là fact có kích thước n + 1, đặt fact [0]:=1
- cho tôi trong phạm vi từ 1 đến n
- fact [i]:=fact [i - 1] * i
- giảm k đi 1
- for i:=n - 1 xuống 0
- idx:=k / fact [i]
- ans:=ans + Applications [idx]
- for j:=idx, j + 1
- ứng viên [j]:=ứng viên [j + 1]
- k:=k mod fact [i]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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);
} Đầu vào
4 9
Đầu ra
2314