LeetCode-Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

预先把1-9的阶乘都算出来，剩下就可以简单粗暴了

class Solution {
public:
    
    string getPermutation(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> per;
        if(n==0) return"";
        if(n==1) return"1";
        per.resize(9);
        per[0]=1;
        k--;
        for(int i=1;i<9;i++){
            per[i]=per[i-1]*(i+1);
        }
        k=k%per[n-1];
        vector<int> vvv;
        vvv.resize(9);
        string ret="";
        for(int i=0;i<9;i++)vvv[i]=i+1;
        for(int i=0;i<n-1;i++){
            int ind=n-2-i;
            int d=k/per[ind];
            k=k%per[ind];
            for(int j=0;j<9;j++){
                if(vvv[j]!=-1){
                    if(d!=0)d--;
                    else{
                        ret+='0'+vvv[j];
                        vvv[j]=-1;
                        break;
                    }
                }
            }
        }
        for(int j=0;j<9;j++){
            if(vvv[j]!=-1){
                ret+='0'+vvv[j];
                vvv[j]=-1;
                break;
            }
        }
        return ret;
    }
};