LeetCode-Permutation Sequence

目的：
取第k个序列，见注解

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        vector<char> ps{'1','2','3','4','5','6','7','8','9'};
        vector<int> fib(n+1,1);
        int tmp=1;
        for(int i=1;i<=n;++i){
            tmp *= i;
            fib[i] = tmp;
        }
        /*
        n--：
        123
        132
        213
        231
        312
        321
        n个数值：n!个序列，对于一个n个数值的排序，第k个排序，其第一位取决于k/per(n-1)
        如上：n=3 每个数值出现的次数是per(n-1)，依次出现
        如上123 132，固定了第一位之后123，132，其中2 3各出现per(1)次
        因此可以通过k/per(n-1)确定n个数值排序的第一位
        
        k--：
        k=2时，per(2)=2,k/per(2)=1，则会取了ps[1]，实际应取ps[0],只有在k%per[n-1]>0时才需要取下一个
        */
        int pos=n-1;
        k--;
        while(pos>=0){
            /*
            index: 确定第n-pos-1位，k/fib[pos]，确定此位的大小
            */
            int index = k/fib[pos];
            res.append(1,ps[index]);
            ps.erase(ps.begin()+index);
            k = k%fib[pos];
            pos--;
        }
        return res;
    }
};