60.排列序列

排列序列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出：”213”

示例 2：

输入：n = 4, k = 9
输出：”2314”

提示：

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

解析

数学法：逐位确定，每位用 k / (n-1)! 确定选哪个数。

var getPermutation = function (n, k) {
  const nums = [];
  let factorial = 1;
  for (let i = 1; i <= n; i++) { nums.push(i); factorial *= i; }
  k--; // 转为 0-indexed
  let result = '';
  for (let i = n; i >= 1; i--) {
    factorial /= i;
    const idx = Math.floor(k / factorial);
    result += nums[idx];
    nums.splice(idx, 1);
    k %= factorial;
  }
  return result;
};