LeetCode 60. 排列序列【数学,逆康托展开】困难

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

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

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

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

示例 1：

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

示例 2：

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

示例 3：

输入：n = 3, k = 1
输出："123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

解法 逆康托展开

要想解决本题，首先需要了解一个简单的结论：对于 $n$ 个不同的元素（例如数 $1,2,\cdots ,n$ ），它们可以组成的排列总数目为 $n!$ 。

对于给定的 $n$ 和 $k$ ，不妨从左往右确定第 $k$ 个排列中的每一个位置上的元素到底是什么。

我们首先确定排列中的首个元素 $a_1$ 。根据上述的结论，我们可以知道：

• 以 $1$ 为 $a_1$ 的排列一共有 $(n-1)!$ 个；
• 以 $2$ 为 $a_1$ 的排列一共有 $(n-1)!$ 个；
• $\cdots$
• 以 $n$ 为 $a_1$ 的排列一共有 $(n-1)!$ 个。

由于我们需要求出从小到大的第 $k$ 个排列，因此：

• 如果 $k\le (n-1)!$ ，我们就可以确定排列的首个元素为 $1$ ；
• 如果 $(n-1)!<k\le 2\cdot (n-1)!$ ，我们就可以确定排列的首个元素为 $2$ ；
• $\cdots$
• 如果 $(n-1)\cdot (n-1)!<k\le n\cdot (n-1)!$ ，我们就可以确定排列的首个元素为 $n$ 。

因此，第 $k$ 个排列的首个元素就是：
$$a_1=\lfloor \frac{k-1}{(n-1)!}\rfloor +1$$
其中 $\lfloor x\rfloor$ 表示将 $x$ 向下取整。

当我们确定了 $a_1$ 后，如何使用相似的思路，确定下一个元素 $a_2$ 呢？实际上，我们考虑以 $a_1$ 为首个元素的所有排列：

• 以 $[1,n]\backslash a_1$ 最小的元素为 $a_2$ 的排列一共有 $(n-2)!$ 个；
• 以 $[1,n]\backslash a_1$ 次小的元素为 $a_2$ 的排列一共有 $(n-2)!$ 个；
• $\cdots$
• 以 $[1,n]\backslash a_1$ 最大的元素为 $a_2$ 的排列一共有 $(n-2)!$ 个；

其中 $[1,n]\backslash a_1$ 表示包含 $1,2,\cdots n$ 中除去 $a_1$ 以外元素的集合。这些排列从编号 $(a_1-1)\cdot (n-1)!$ 开始，到 $a_1\cdot (n-1)!$ 结束，总计 $(n-1)!$ 个，因此第 $k$ 个排列实际上就对应着这其中的第
$$k^{\prime }=(k-1)\mathrm{mod}(n-1)!+1$$
个排列。这样一来，我们就把原问题转化成了一个完全相同但规模减少 $1$ 的子问题：求 $[1,n]\backslash a_1$ 这 $n-1$ 个元素组成的排列中，第 $k^{\prime }$ 小的排列。

算法：

1. 设第 $k$ 个排列为 $a_1,a_2,\cdots ,a_n$ ，我们从左往右地确定每一个元素 $a_i$​ 。我们用数组 $\text{valid}$ 记录每一个元素是否被使用过。
2. 我们从小到大枚举 $i$ ：
   1. 我们已经使用过了 $i-1$ 个元素，剩余 $n-i+1$ 个元素未使用过，每一个元素作为 $a_i$ 都对应着 $(n-i)!$ 个排列，总计 $(n-i+1)!$ 个排列；
   2. 因此在第 $k$ 个排列中，$a_i$ 即为剩余未使用过的元素中第 $\lfloor \frac{k-1}{(n-i)!}\rfloor +1$ 小的元素；
   3. 在确定了 $a_i$ 后，这 $n-i+1$ 个元素的第 $k$ 个排列，就等于 $a_i$ 之后跟着剩余 $n-i$ 个元素的第 $(k-1)\mathrm{mod}(n-i)!+1$ 个排列。

在实际的代码中，我们可以首先将 $k$ 的值减少 $1$，这样可以减少运算，降低代码出错的概率。对应上述的后两步，即为：

• 因此在第 $k$ 个排列中，$a_i$​ 即为剩余未使用过的元素中第 $\lfloor \frac{k}{(n-i)!}\rfloor +1$ 小的元素；
• 在确定了 $a_i$ 后，这 $n-i+1$ 个元素的第 $k$ 个排列，就等于 $a_i$ 之后跟着剩余 $n-i$ 个元素的第 $k\mathrm{mod}(n-i)!$ 个排列。

实际上，这相当于我们将所有的排列从 $0$ 开始进行编号。

class Solution {
public:
    string getPermutation(int n, int k) {
        --k;
        int factory[10] = {1};
        for (int i = 1; i < n; ++i) factory[i] = factory[i - 1] * i;
        bool vis[10] = {false};

        string ans;
        for (int i = n - 1; i >= 0; --i) {
            int num = k / factory[i];
            k = k % factory[i];
            for (int j = 1; j <= n; ++j) {
                if (!vis[j]) {
                    if (num-- == 0) {
                        ans += '0' + j;
                        vis[j] = true;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$