Permutation Sequence

mail@pastecode.io avatar
unknown
c_cpp
a year ago
863 B
6
Indexable
Never
class Solution {
    vector<int> fact;
public:
    string getPermutation(int n, int k) {
        fact.resize(n + 1, 1);
        for(int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }

        vector<bool> used(n + 1, false);
        string ans = "";
        for(int i = 1; i <= n; i++) {
            int rank = 1;
            while(k > fact[n - i]) {
                k -= fact[n - i];
                rank++;
            }
            char add;
            for(int j = 1; j <= n; j++) {
                if(!used[j]) {
                    rank--;
                }
                if(rank == 0) {
                    used[j] = true;
                    add = '0' + j;
                    break;
                }
            }
            ans += add;            
        }
        return ans;       
    }
};