[Lc]60第k个排列

题目

题解

这道题直接找规律，比较难自己想通，该解法出自grandyang

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;//定义res保存结果
        string nums = "123456789";//num用来提取最后返回的字符型数字
        vector<int> factorial(n,1);//factorial用来存n的阶乘
        for(int i=1; i<n; ++i) factorial[i] = factorial[i-1] * i;//注意阶乘从0开始到n-1，！！这里得用++i,否则会溢出
        k--;//k--获得k-1用于后续计算，因为k后续用于在数组中取值，数组是从0开始的
        for(int i=n; i>=1; --i){//迭代阶乘数组中的所有值
            int j = k/factorial[i-1];//第一个位置每个数字反复出现的次数是n-1！，以此类推
            k %= factorial[i-1];//k取余
            res.push_back(nums[j]);//加入第一步得到的数字
            nums.erase(j,1);//nums中剔除已经加入的数字
        }
        return res;
    }
};