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

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

“123”
“132”
“213”
“231”
“312”
“321”

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

思路

  1. –k，将 k 视为从 0 开始的顺序，满足 k < n!
  2. 若 k >= (n - 1)!，那么第一位一定是 k / (n - 1)!，否则第一位一定是 1
  3. 维护 indexes，作为待选的序列，从 n - 1 开始递减遍历，每次选出一个序号，并从 indexes 中剔除，最终可以得出结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var getPermutation = function (n, k) {
  const T = [1]
  for (let i = 1; i < n; ++i) {
    T[i] = T[i - 1] * i
  }
  const indexes = new Array(n).fill(null).map((_, index) => index + 1)
  const items = []
  --k
  for (let i = n - 1; i >= 1 && k >= 0; --i) {
    if (k >= T[i]) {
      const factor = Math.floor(k / T[i])
      items.push(indexes[factor])
      indexes.splice(factor, 1)
      k -= factor * T[i]
    } else {
      items.push(indexes[0])
      indexes.splice(0, 1)
    }
  }
  return [...items, ...indexes].join('')
}