原题：排列序列

思路：找到规律，拆解独立步骤，递归

思路

观察题目我们可以看出是按照数字从小到大的顺序排列组合的

所以不妨拆分成按照位置求每一位

举个例子：

1
2
3
4
5
6
7
# 当 n = 3 时
123
132
213
231
312
321

稍微观察就可以找到一个规律，只看第一位，第 k 个数为当前未使用数的第 (k ÷ 其余位组合种类) 个数
比如 k = 4，那么就是 4 ÷ 2(两位数的组合数) = 2(未使用数中的第二个)，因为没有任何数字被使用过，所以第一位数是 2

1. 初始化

我们求组合数会用到阶乘，同时还需要跳过已经使用过的数字

从而需要使用两张哈希表 calMap、resultMap

1
2
3
4
// 缓存阶乘结果
const calMap = {};
// 缓存已经填入的数字
const resultMap = {};

同时准备一个能缓存结果的阶乘函数 calNum

1
2
3
4
5
6
7
8
9
10
11
12
13
function calNum(n) {
  // 如果有缓存就直接返回
  if (calMap[n] !== undefined) return calMap[n];
  let res = 1;
  let i = 1;
  // 计算 n 的同时会把 n-1, n-2, n-3 ... 1 的阶乘同时缓存好
  while (i <= n) {
    res *= i;
    calMap[n] = res;
    i++;
  }
  return res;
}

2. 实现找到当前位数字的方法

  1. 计算是第几个数
1
2
// 如果是最后一个数，那么只找一步，否则找 k / 第二位之后的组合个数 向上取整的步数
let step = n === 1 ? 1 : Math.ceil(k / calNum(n - 1));
  1. 进入循环寻找未使用的第 step 个数字

这里用到两个指针，i 表示数字，j 记录步数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
for (let i = 0, j = 0; ; ) {
  // 步数足够就是说找到了
  if (j === step) {
    // 记录数字已被使用
    resultMap[i] = true;
    // 如果是最后一个数
    if (n === 1) {
      // 直接返回当前结果
      return i.toString();
    } else {
      // 否则返回当前和后续递归的结果
      /**
       * 【重要】
       * n - 1 很容易理解，但是 k 比较难理解，接着上面的例子说
       * 我们找第 3 个数也就是 213，假设已经确认了第一位 2，后续需要找的是第二三位的组合，所以 n - 1 = 2
       * 那么我们可以看作是在 [13, 31] 中找第 k 个数
       * 仔细观察可以知道 k % (n - 1)!(第二三位的组合数) = 3 % 2 = 1，下一轮的 k 就是 1
       * 但是要注意如果是找第四位即 4 % 2 = 0，这时候也可以观察到模为 0 其实就是找到组合中的最后一位，也就是 k = (n - 1)! = 2
       */
      return i.toString() + deal(n - 1, k % calNum(n - 1) || calNum(n - 1));
    }
  }
  // 没用过的数才记录步数
  i++;
  if (!resultMap[i]) {
    j++;
  }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  // 缓存阶乘结果
  const calMap = {};
  // 缓存已经填入的数字
  const resultMap = {};
  // 阶乘
  function calNum(n) {
    // 如果有缓存就直接返回
    if (calMap[n] !== undefined) return calMap[n];
    let res = 1;
    let i = 1;
    // 计算 n 的同时会把 n-1, n-2, n-3 ... 1 的阶乘同时缓存好
    while (i <= n) {
      res *= i;
      calMap[n] = res;
      i++;
    }
    return res;
  }
  function deal(n, k) {
    /**
     * 【思路】
     * 123
     * 132
     * 213
     * 231
     * 312
     * 321
     * 稍微观察就可以找到一个规律，只看第一位，第 k 个数为当前未使用数的第 (k ÷ 其余位组合种类) 个数
     * 比如 k 为 4，那么就是 4 ÷ 2(两位数的组合数) = 2(未使用数中的第二个)，那么就是 2
     * 接着记录已经使用过的数字，递归寻找剩余数
     */
    // 如果是最后一个数，那么只找一步，否则找 k / 第二位之后的组合个数 向上取整的步数
    let step = n === 1 ? 1 : Math.ceil(k / calNum(n - 1));
    for (let i = 0, j = 0; ; ) {
      // 步数足够就是说找到了
      if (j === step) {
        // 记录数字已被使用
        resultMap[i] = true;
        // 如果是最后一个数
        if (n === 1) {
          // 直接返回当前结果
          return i.toString();
        } else {
          // 否则返回当前和后续递归的结果
          /**
           * 【重要】
           * n - 1 很容易理解，但是 k 比较难理解，接着上面的例子说
           * 我们找第 3 个数也就是 213，假设已经确认了第一位 2，后续需要找的是第二三位的组合，所以 n - 1 = 2
           * 那么我们可以看作是在 [13, 31] 中找第 k 个数
           * 仔细观察可以知道 k % (n - 1)!(第二三位的组合数) = 3 % 2 = 1，下一轮的 k 就是 1
           * 但是要注意如果是找第四位即 4 % 2 = 0，这时候也可以观察到模为 0 其实就是找到组合中的最后一位，也就是 k = (n - 1)! = 2
           */
          return i.toString() + deal(n - 1, k % calNum(n - 1) || calNum(n - 1));
        }
      }
      // 没用过的数才记录步数
      i++;
      if (!resultMap[i]) {
        j++;
      }
    }
  }
  return deal(n, k);
};