YEZAELP

LeetCode: Permutation Sequence

Dec 1st, 2021 (edited)
630
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// O(n^2)
  2. class Solution {
  3. public:
  4.     string getPermutation(int n, int k) {
  5.         string ans;
  6.  
  7.         int fac[n + 1];
  8.         fac[0] = 1;
  9.         for(int i=1;i<=n;i++) fac[i] = fac[i - 1] * i;
  10.  
  11.         vector <int> num;
  12.         for(int i=0;i<=n;i++) num.push_back(i);
  13.  
  14.         for(n--;n>=1;n--){
  15.             int idx = k / fac[n];
  16.             if(k % fac[n] != 0) idx ++;
  17.             ans += num[idx] + '0';
  18.             num.erase(num.begin() + idx);
  19.             k %= fac[n];
  20.             if(k == 0) k = fac[n];
  21.         }
  22.         ans += num[1] + '0';
  23.         return ans;
  24.     }
  25. };
  26.  
  27. /// backtracking
  28. class Solution {
  29. public:
  30.     string ans;
  31.     bool mark[10];
  32.     int N, K, cntk;
  33.     bool found;
  34.     string cur;
  35.     void f(int n){
  36.         if(found) return;
  37.         if(n == N){
  38.             cntk ++;
  39.             if(cntk == K){
  40.                 ans += cur;
  41.                 found = true;
  42.             }
  43.             return;
  44.         }
  45.         for(int i=1;i<=N;i++){
  46.             if(!mark[i]){
  47.                 mark[i] = true;
  48.                 cur += i + '0';
  49.                 f(n + 1);
  50.                 mark[i] = false;
  51.                 cur.pop_back();
  52.             }
  53.         }
  54.     }
  55.     string getPermutation(int n, int k) {
  56.         N = n, K = k;
  57.         f(0);
  58.         return ans;
  59.     }
  60. };
RAW Paste Data