排列序列

题目

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

按大小顺序列出所有排列情况, 并一一标记, 如当 n = 3 时, 所有排列为: "123", "132", "213", "231", "312", "321"

给定 n 和 k, 返回第 k 个排列.

提示:

• 1 <= n <= 9
• 1 <= k <= n!

示例

输入: (n = 3), (k = 3)

输出: '213'

输入: (n = 4), (k = 9)

输出: '2314'

输入: (n = 3), (k = 1)

输出: '123'

题解

初始想法是借鉴 46. 全排列, 获取第 k 个生成的 track, 然而 hard 毕竟是 hard, 果然就超时了...

JavaScript-回溯(超时)

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  let res = ''
  let count = 0

  const dfs = (track) => {
    if (track.length === n) {
      count += 1

      if (count === k) {
        res = track.join('')
        return
      }
    }

    for (let i = 1; i <= n; i++) {
      if (!track.includes(i)) {
        track.push(i)
        dfs(track)
        track.pop()
      }
    }
  }

  dfs([])

  return res
}

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  // 计算阶乘数组
  const factorial = [1]
  for (let i = 1; i <= n; i++) {
    factorial[i] = factorial[i - 1] * i
  }

  // 初始化候选数字数组
  const numbers = []
  for (let i = 1; i <= n; i++) {
    numbers.push(i)
  }

  // k需要调整为0基数
  k--

  let result = ''

  for (let i = n; i >= 1; i--) {
    // 确定当前位使用哪个数字
    const index = Math.floor(k / factorial[i - 1])
    result += numbers[index]

    // 移除选定的数字
    numbers.splice(index, 1)

    // 更新k
    k %= factorial[i - 1]
  }

  return result
}