Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// O(n^2)
- class Solution {
- public:
- string getPermutation(int n, int k) {
- string ans;
- int fac[n + 1];
- fac[0] = 1;
- for(int i=1;i<=n;i++) fac[i] = fac[i - 1] * i;
- vector <int> num;
- for(int i=0;i<=n;i++) num.push_back(i);
- for(n--;n>=1;n--){
- int idx = k / fac[n];
- if(k % fac[n] != 0) idx ++;
- ans += num[idx] + '0';
- num.erase(num.begin() + idx);
- k %= fac[n];
- if(k == 0) k = fac[n];
- }
- ans += num[1] + '0';
- return ans;
- }
- };
- /// backtracking
- class Solution {
- public:
- string ans;
- bool mark[10];
- int N, K, cntk;
- bool found;
- string cur;
- void f(int n){
- if(found) return;
- if(n == N){
- cntk ++;
- if(cntk == K){
- ans += cur;
- found = true;
- }
- return;
- }
- for(int i=1;i<=N;i++){
- if(!mark[i]){
- mark[i] = true;
- cur += i + '0';
- f(n + 1);
- mark[i] = false;
- cur.pop_back();
- }
- }
- }
- string getPermutation(int n, int k) {
- N = n, K = k;
- f(0);
- return ans;
- }
- };
Add Comment
Please, Sign In to add comment