060.排列序列

作者：沉默王二
发布时间：2022-11-19T11:29:31.307+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

060.排列序列

题意

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

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

• "123"
• "132"
• "213"
• "231"
• "312"
• "321"

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

难度

困难

示例

示例 1：

输入：n = 3, k = 3

示例 2：

输入：n = 4, k = 9

示例 3：

输入：n = 3, k = 1

分析

这题如果采用最原始的暴力枚举，就需要从小到大依次找出k个排列，然后才能得出答案，就相当于我们需要遍历第k个排列前的整棵解答树。

但这是排列，我们能不能用一些数学方法来加快这个过程呢？

通过上图我们可以看到，这是生成所有排列的一个解答树。

它的深度，以及每层节点的分叉数量都是固定的，所以……

我们是不是能够不用遍历这个子树，便可以知道子树的大小？从而确定所求的第k大的排列是否会在这个子树内出现？

那么既然知道了这个规律，我们就来总结一下每一层的分叉数的规律——第一层3个，第二层 2个，第三层1个……再把这些分叉数乘起来，是不是就是对应的子树的大小了？

是的，其实就是一个阶乘的关系，那么就可以通过这个来快速跳过第k个排列之前的排列，不用再去依次遍历到整个解答树的叶子节点，节省了大量的时间。

class Solution {

    int[] fac;    StringBuilder res;    void DFS(int step,int n,int k){        if(step == n){            return ;        }        int cnt = fac[n - 1 - step];//现在是第step层，如果k大于子树大小，就直接跨过        for(int i = 1;i <= n;i++){            if(used[i]){                continue;            }            if(cnt < k){//跨过该子树                k -= cnt;                continue;            }            //找到答案所在的子树了            res.append(i);            used[i] = true;            DFS(step + 1,n,k);            return ;        }    }    public String getPermutation(int n, int k) {        res = new StringBuilder();        used = new boolean[n + 1];        fac = new int[n + 1];        fac[0] = 1;        for(int i = 1;i <= n;i++) {            fac[i] = fac[i - 1] * i;        }        DFS(0,n,k);        return res.toString();    }}

总结

其实本题并不算太难，主要是观察出子树大小的规律，从而找出快速跳过当前子树的办法，这才是本题的重点。

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1000 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

060.排列序列

题意

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

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

• "123"
• "132"
• "213"
• "231"
• "312"
• "321"

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

难度

困难

示例

示例 1：

输入：n = 3, k = 3

示例 2：

输入：n = 4, k = 9

示例 3：

输入：n = 3, k = 1

分析

这题如果采用最原始的暴力枚举，就需要从小到大依次找出k个排列，然后才能得出答案，就相当于我们需要遍历第k个排列前的整棵解答树。

但这是排列，我们能不能用一些数学方法来加快这个过程呢？

通过上图我们可以看到，这是生成所有排列的一个解答树。

它的深度，以及每层节点的分叉数量都是固定的，所以……

我们是不是能够不用遍历这个子树，便可以知道子树的大小？从而确定所求的第k大的排列是否会在这个子树内出现？

那么既然知道了这个规律，我们就来总结一下每一层的分叉数的规律——第一层3个，第二层 2个，第三层1个……再把这些分叉数乘起来，是不是就是对应的子树的大小了？

是的，其实就是一个阶乘的关系，那么就可以通过这个来快速跳过第k个排列之前的排列，不用再去依次遍历到整个解答树的叶子节点，节省了大量的时间。

class Solution {

    int[] fac;    StringBuilder res;    void DFS(int step,int n,int k){        if(step == n){            return ;        }        int cnt = fac[n - 1 - step];//现在是第step层，如果k大于子树大小，就直接跨过        for(int i = 1;i <= n;i++){            if(used[i]){                continue;            }            if(cnt < k){//跨过该子树                k -= cnt;                continue;            }            //找到答案所在的子树了            res.append(i);            used[i] = true;            DFS(step + 1,n,k);            return ;        }    }    public String getPermutation(int n, int k) {        res = new StringBuilder();        used = new boolean[n + 1];        fac = new int[n + 1];        fac[0] = 1;        for(int i = 1;i <= n;i++) {            fac[i] = fac[i - 1] * i;        }        DFS(0,n,k);        return res.toString();    }}

总结

其实本题并不算太难，主要是观察出子树大小的规律，从而找出快速跳过当前子树的办法，这才是本题的重点。

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1000 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

060.排列序列

题意

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

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

• "123"
• "132"
• "213"
• "231"
• "312"
• "321"

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

难度

困难

示例

示例 1：

输入：n = 3, k = 3

示例 2：

输入：n = 4, k = 9

示例 3：

输入：n = 3, k = 1

分析

这题如果采用最原始的暴力枚举，就需要从小到大依次找出k个排列，然后才能得出答案，就相当于我们需要遍历第k个排列前的整棵解答树。

但这是排列，我们能不能用一些数学方法来加快这个过程呢？

通过上图我们可以看到，这是生成所有排列的一个解答树。

它的深度，以及每层节点的分叉数量都是固定的，所以……

我们是不是能够不用遍历这个子树，便可以知道子树的大小？从而确定所求的第k大的排列是否会在这个子树内出现？

那么既然知道了这个规律，我们就来总结一下每一层的分叉数的规律——第一层3个，第二层 2个，第三层1个……再把这些分叉数乘起来，是不是就是对应的子树的大小了？

是的，其实就是一个阶乘的关系，那么就可以通过这个来快速跳过第k个排列之前的排列，不用再去依次遍历到整个解答树的叶子节点，节省了大量的时间。

class Solution {

    int[] fac;    StringBuilder res;    void DFS(int step,int n,int k){        if(step == n){            return ;        }        int cnt = fac[n - 1 - step];//现在是第step层，如果k大于子树大小，就直接跨过        for(int i = 1;i <= n;i++){            if(used[i]){                continue;            }            if(cnt < k){//跨过该子树                k -= cnt;                continue;            }            //找到答案所在的子树了            res.append(i);            used[i] = true;            DFS(step + 1,n,k);            return ;        }    }    public String getPermutation(int n, int k) {        res = new StringBuilder();        used = new boolean[n + 1];        fac = new int[n + 1];        fac[0] = 1;        for(int i = 1;i <= n;i++) {            fac[i] = fac[i - 1] * i;        }        DFS(0,n,k);        return res.toString();    }}

总结

其实本题并不算太难，主要是观察出子树大小的规律，从而找出快速跳过当前子树的办法，这才是本题的重点。

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1000 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412