题目描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。

样例

示例 1:
输入: n = 3, k = 3
输出: "213"

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

算法1

(模拟) $O(n^2)$

举个例子： $n = 3, k = 4$
在$xxx$中寻找第$4$个排列；
第一个数字为$1$到$3$的$xxx$各有$2!$个，所以第一个数字为$2$;
接下来在$2xx$中寻找第$4 - 2 * 1= 2$个排列；
第二个数字为$1$或者$3$的$2xx$各有$1!$个($2$已经用过了，不能用了)，所以第二个数字为$3$;
接下来在$23x$中寻找第$4 - 2 * 1 - 1 * 1= 1$个排列；
第三个数字为$1$的$23x$仅剩$1$个($2$、$3$已经用过了，不能用了)，所以第三个数字为$1$。

时间复杂度

看代码，两层循环，时间复杂度$O(n^2)$

参考文献

C++ 代码

class Solution {
public:
    string getPermutation(int n, int k) {
        // 记录使用过的数字
        vector<bool> st(n + 1);
        // 预处理阶乘
        vector<int> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) f[i] = f[i - 1] * i;

        string res;

        for (int i = 0; i < n; ++i){
            // 计算应该取剩余可用数字中的第几个数字
            int fac = f[n - 1 - i], g = (k - 1) / fac;

            // 确定剩余可用数字中的第g个数字是几
            int num = 1, cnt = 0;
            while (true){
                while (num <= n && st[num]) ++num;
                if (cnt == g) break;
                else ++cnt, ++num;
            }

            // 将该数字加入答案，并标记为使用过了
            st[num] = true;
            res.push_back(num + '0');
            // 更新k
            k -= fac * g;
        }

        return res;
    }
};