原题
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"给定 n 和 k，返回第 k 个排列。
说明：
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"示例 2:
输入: n = 4, k = 9
输出: "2314"解法
按照题目所描述的，其实就是按照排列规律，找出相应的数字。
每一位上可以存在的可能数字范围逐渐减少，因此我们需要记录一下当前用过哪些数字。
每一位上前缀数字最终对应的可能性也是一个全排列，比如 n 为4时，当第1位定下来一个数字，其对应的所有数字组合有 3!，当第2位定下来后，其对应的数字组合就是2!。当你确认的数字越多，其组合也越少。
直接上代码：
class Solution {
// 当前数字是否用过，默认为false，代表没有用过
boolean[] used;
public String getPermutation(int n, int k) {
used = new boolean[n];
int all = 1;
for (int i = n - 1; i > 1; i--) {
all *= i;
}
StringBuilder sb = dfs(n, all, k);
return sb.toString();
}
/**
* n:当前还剩几个数字没有添加
* all:为了计算出当前数字属于第几组，例如n等于5时，all是4!，这样k/n就知道是第几组了
* k:所求结果是当前组的第几个
*/
public StringBuilder dfs(int n, int all, int k) {
// 组内偏移量
int offset = k % all;
// 当前是第几组
int groupIndex = k / all + (offset == 0 ? 0 : 1);
// 在当前没有被访问过的数字里，找第groupIndex个数字
int i = 0;
for (; i < used.length && groupIndex > 0; i++) {
if (!used[i]) {
groupIndex--;
}
}
// 用当前数字
StringBuilder result = new StringBuilder().append(i);
// 标记当前数字已经用过
used[i - 1] = true;
// 说明是最后一个数字
if (n == 1) {
return result;
}
// 确认一位数字后，其对应的可能性就在减少
return result.append(dfs(n - 1, all / (n - 1), (offset == 0 ? all : offset)));
}
}提交OK，执行用时：2ms，内存消耗：34.4MB。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题应该主要就是找规律了，确认好边界情况就应该没什么问题。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。
公众号：健程之道
