题目描述

给出集合 [1,2,3,…,n] ，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当n = 3时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

来源，leetcode 每日一题 第K个排列

给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

解题思路

1. 以1-n为首的排列共有 (n-1)! 个
2. 通过 k mod (n-1)! 可以确定出一个最开始的范围
3. 然后在 (n-1) 个数的排列中，继续缩小范围，直到范围不能再小
4. 至此，排列已经确定

代码

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorial(n);
        factorial[0] = 1;
        // 计算 i个数可能的排列数量
        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }
        --k;
        string ans;
        vector<int> valid(n + 1, 1);
        for (int i = 1; i <= n; ++i) {
            // 计算第i个数是什么
            int order = k / factorial[n - i] + 1;
            for (int j = 1; j <= n; ++j) {
                order -= valid[j];
                // 判断这个数是否有用过
                if (!order) {
                    ans += (j + '0');
                    valid[j] = 0;
                    break;
                }
            }
            // k = k - k/factorial[n-i] * factorial[n-i]
            k %= factorial[n - i];
        }   
        return ans;     
    }
};