字节尿性,康托展开求第K个排列!

01/29 08:04
阅读数 35

字节尿性,康托展开求第K个排列!


今天是小浩算法 “365刷题计划” 第 109 天。继续为大家讲解 leetcode 第 60 题,是一道中等难度的题目。

排列类别的问题主要就两个,一个是全排列:

小白真能看一篇文章就学会全排列算法吗?

另一个就是本题(两个题在剑指offer都出现了):

字节尿性,康托展开求第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"

字节尿性,康托展开求第K个排列!

示例 2:

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

02

PART

题解分析


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


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

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

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

公式是这样的:

字节尿性,康托展开求第K个排列!

解释一哈:

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

字节尿性,康托展开求第K个排列!

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

字节尿性,康托展开求第K个排列!

关键是这个 字节尿性,康托展开求第K个排列! ,这个其实就是看原数的第 i 位在当前未出现的元素中是排在第几个。

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

解释:第一个数是 4,比 4 小的并且还没有出现过的数有 3 个(123),第二个数是 1,比 1 小的并且还没有出现过的数为 0 个。第三个数是 3,比 3 小的并且还没有出现过的数为 1。第四个数是 2 ,比 2 小的并且还没有出现过的数为 0 个。

有 X = 33!+ 02!+ 11!+ 00!= 19,此时的序号为 19+1 = 20。还不明白的看下下面这个图:

字节尿性,康托展开求第K个排列!

然后我们把上面的东西反着来,就叫做 逆康托展开。换句话说,就是给我们了 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();
    }
}

字节尿性,康托展开求第K个排列!

03

PART

相似题目


说是相似题目,但是其实下面两个题目我都是用回溯来求解的啦。算是通用解法吧~大家有兴趣也可以用回溯来解下本题。

小白学着求全排列

小白学着求子集(快手)

我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部