题目大意：
第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"
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： 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.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-60-permutation-sequence-解题思路分析/