60. Permutation Sequence

题目链接

https://leetcode.com/problems/permutation-sequence/

解题思路

n个数要求第k个排列，可以先根据k在n个数里面先确定第一个数并更新k，之后问题就变成了在剩下的n-1数里面找更新后的第k个排列的子问题。

代码

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> fac(n + 1, 0);
        vector<int> nums(n);

        //fac[i]表示i的阶乘 num[i]是i+1
        fac[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fac[i] = fac[i - 1] * i;
            nums[i - 1] = i;
        }

        string ans;
        while (!nums.empty()) {
            //在nums数组里确定取哪个数
            int &t = fac[nums.size() - 1];
            //i表示取的nums数组里的第几个数，从1开始
            int i = k / t;
            if (k % t != 0 || i == 0) {
                i++;
            }
            //更新k
            k = k - (i - 1) * t;
            ans.push_back((char) (nums[i - 1] + '0'));
            nums.erase(nums.begin() + i - 1);
        }
        return ans;
    }
};