LEETCODE 60. Permutation Sequence 解题思路分析

题目大意:

第k个排列

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

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

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

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

说明:

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

示例 1:

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

示例 2:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=60

解题思路分析:

本题与之前我们讲过的一篇文章十分相似,LEETCODE 440. K-th Smallest in Lexicographical Order解题思路分析,当我们刷题数量到达一定程度之后,再遇到的新题实际上都是原先做过老题的翻新版本,因此大家需要学会举一反三。

回到本题,对于给定的集合n,其所有元素共有 n! 种排列。这个概念并不难理解,因为第一位我们有n种选择(每个数都可以选),第二位不能选择第一位选过的数字,因此可选择的数字有n-1种,同理,第三位不能选前两位选过的数字,即可选的数字有n-2种,以此类推直到最后一位,我们只有一个数字可以选择,这样算下来一共的可能性就是:n*(n-1)*(n-2)*…2*1=n!。

本题我们同样可以将这种排列看做是一个树形结构(字典树),比如n={1,2,3,4}时,我们可以将字典树构建成为下图:

由于时间原因,3和4根节点下面的路径被我省略掉了。我们以根节点1举例,以1开头的排序方式有6种,分别是1下面的每条路径,另外以2,3,4开头的路径也分别有6种,总共的路径一共是4*6=24种,这也等于4的阶乘。

解题时,我们先将集合中的每一个数字看做是一个根节点,因此,以上图为例,我们一共有4个根节点,因为总共有4的阶乘种路径(排列方式),因此,每个根节点下应该是24 / 4 = 6条路径。这时,我们用题目给出的k与6进行比较,如果k在1-6之间,那么我们可以将返回结果的范围缩小至第一个根节点的树下。同理,如果k在7-12之间,我们就能确定返回结果在第二个根节点的树下。比如k等于11,那么返回结果一定在根节点为2的树下,换句话说,我们的返回结果的首位是2

接下来,我们求出k与6的余数等于5,这代表了,我们要找的结果是根节点为2的树下的第5条路径。这样问题就转化为,我们有1,3,4三个根节点,求k等于5时的返回结果。这与原问题非常的类似,我们找到了原问题的一个子问题(递归)。与原问题同理,因为1,3,4每个根节点下有2条路径,因此,当k等于5时,返回结果应该在第三个根节点4的树下。此时我们得到了返回结果的第二位是4。

以此类推我们就能得到返回结果的所有位。

实现代码:

boolean[] used; // 为了防止重复,记录已经使用过的数字
public String getPermutation(int n, int k) {
    int pathCount = 1;
    // 统计所以每个根节点下的路径数目
    // 因为所有路径数目是n的阶乘,我们一共有n个根节点
    // 所以每个根节点下的路径数目:n-1的阶乘
    for(int i=2;i<n;i++) pathCount*=i;
    // 初始化数组
    used = new boolean[n+1];
    // 递归求解
    return help(pathCount,n-1,n,k).toString();
}
// pathCount:每个根节点下所有路径数
// childCount:根节点下一层子节点数量
// 返回:所有根节点的所有路径中的第k条路径
StringBuilder help(int pathCount,int childCount,int n,int k){
    if(childCount<0) return new StringBuilder();
    int branchIndex=1;
    // 计算k在第几个根节点下
    while(k>pathCount){
        k-=pathCount;
        branchIndex++;
    }
    int index=0;
    StringBuilder sb= new StringBuilder();
    // 找到第branchIndex个没有使用过的数字
    for(int i=1;i<=n;i++){
        if(!used[i]) index++;
        if(index==branchIndex){
            sb.append(i); // 将该数字加入返回结果
            used[i]=true; // 记录该数字已经使用过
            break;
        }
    }
    // 范围缩小至选定的数字(根节点),
    // 计算该根节点下每个子节点的路径数量
    if(childCount>0) pathCount/=childCount;
    // 每个子节点的子节点数量减一
    childCount--;
    // 递归
    sb.append(help(pathCount,childCount,n,k));
    return sb;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 97.72% of Java online submissions for Permutation Sequence.

Memory Usage: 37.3 MB, less than 20.83% of Java online submissions for Permutation Sequence.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-60-permutation-sequence-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。