60.排列序列
60. 排列序列
题意
给出集合[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"
分析
这题如果采用最原始的暴力枚举，就需要从小到大依次找出 k 个排列，然后才能得出答
案，就相当于我们需要遍历第 k 个排列前的整棵解答树。
但这是排列，我们能不能用一些数学方法来加快这个过程呢？
1668828434163-89fed58b-f85b-4299-b5ae-51d39d04908d.png
通过上图我们可以看到，这是生成所有排列的一个解答树。
它的深度，以及每层节点的分叉数量都是固定的，所以……
我们是不是能够不用遍历这个子树，便可以知道子树的大小？从而确定所求的第 k 大的排
列是否会在这个子树内出现？
那么既然知道了这个规律，我们就来总结一下每一层的分叉数的规律——第一层 3 个，第
二层 2 个，第三层 1 个……再把这些分叉数乘起来，是不是就是对应的子树的大小了？
是的，其实就是一个阶乘的关系，那么就可以通过这个来快速跳过第 k 个排列之前的排
列，不用再去依次遍历到整个解答树的叶子节点，节省了大量的时间。
class Solution {
boolean[] used;
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();
}
}
1668828460434-bd4c6087-f573-415a-a3a6-0c2bdc3ba5a5.png
总结
其实本题并不算太难，主要是观察出子树大小的规律，从而找出快速跳过当前子树的办
法，这才是本题的重点。