字节尿性，康托展开求第K个排列！

另一个就是本题（两个题都出现了）：

01

PART

第K个排列

题目比较绕，耐心点还是可以看懂的~加油！

题目：给出集合 [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"

02

PART

题解分析

这道题目的标签标的数学和回溯算法，所以我们分别用数学和回溯的方法来解题。

从数学方法说起，先讲一下康托展开。

那康托展开是干嘛的？用来计算当前排列在所有由小到大全排列中的顺序。卧槽，不就是本题吗。

听不懂？就是说如果你知道 1234 是序号 1，1243 是 序号2，这个公式就可以直接告诉你 4132 的序号是多少！

公式是这样的：

解释一哈：

这个 X 就是最终的序号值，比实际序号少一位，因为可以看到康托展开第一位计算的值是 0 。

网上看到的很多图可能名次是从 1 开始，这个大家注意一下就行：

关键是这个

，这个其实就是看原数的第 i 位在当前未出现的元素中是排在第几个。

感觉这句话有点拗口，用上面出现的问题解释一下：1234 是序号 1，1243 是 序号 2， 4132 的序号是多少？

解释：第一个数是 4，比 4 小的并且还没有出现过的数有 3 个（123），第二个数是 1，比 1 小的并且还没有出现过的数为 0 个。第三个数是 3，比 3 小的并且还没有出现过的数为 1。第四个数是 2 ，比 2 小的并且还没有出现过的数为 0 个。

有 X = 3*3！+ 0*2！+ 1*1！+ 0*0！= 19，此时的序号为 19+1 = 20。还不明白的看下下面这个图：

然后我们把上面的东西反着来，就叫做 逆康托展开。换句话说，就是给我们了 X 的值，让我们求

。

对于 逆康托展开，我还是给一个例子。比如 nums 还是 1234，我们要找第 15 位。那么要进行以下几步：

• 首先，因为 X 比实际序号少一位，所以我们要用实际序号减1，也就是 15 - 1 = 14。
• 目标值的第一个字符，14 / 3! = 2 ... 2 (商2余2)，没有已使用的字符，第一个字符取在未使用的字符中排增序第3。即3
• 目标值的第二个字符，2 / 2! = 1 ... 0，已使用的字符为3，第二个字符取在未使用的字符中增序排第2。即2
• 目标值的第三个字符，0 / 1! = 0 ... 0，已使用的字符为2和3，第三个字符取在未使用的字符中增序排第1。即1
• 目标值的第三个字符，0 / 0! = 0 ... 0，已使用的字符为1，2和3，第四个字符取在未使用的字符中增序排第1。即4
• 那么要求的这个序列为：3214。
• 可以查下上面的表，发现是正确的。如果看不懂，可以回到上面的例子再看看，其实就是把上面过程倒着来。

最后，我们再将逆康托展开进行应用：

//JAVA
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        // 候选数字
        List<Integer> candidates = new ArrayList<>();
        // 分母的阶乘数
        int[] factorials = new int[n+1];
        factorials[0] = 1;
        int fact = 1;
        for(int i = 1; i <= n; ++i) {
            candidates.add(i);
            fact *= i;
            factorials[i] = fact;
        }
        //预处理
        k -= 1;
        for(int i = n-1; i >= 0; --i) {
            // 计算候选数字的index
            int index = k / factorials[i];
            sb.append(candidates.remove(index));
            k -= index*factorials[i];
        }
        return sb.toString();
    }
}