60.排列序列

链接：60.排列序列
难度：Hard
标签：递归、数学
简介：给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。给定 n 和 k，返回第 k 个排列。

题解 1 - typescript

• 编辑时间：2020-09-05
• 执行用时：5932ms
• 内存消耗：76MB
• 编程语言：typescript
• 解法介绍：遍历所有可能,在达到需要的值时暂停。

function getPermutation(n: number, k: number): string {
  const ans: string[] = [];
  dfs();
  return ans[k - 1];
  function dfs(arr: number[] = [], set: Set<number> = new Set()): void {
    if (ans.length > k - 1) return;
    let f = false;
    for (let i = 1; i <= n; i++) {
      if (set.has(i)) continue;
      f = true;
      set.add(i);
      arr.push(i);
      dfs(arr, set);
      arr.pop();
      set.delete(i);
    }
    if (!f) ans.push(arr.join(''));
  }
}

题解 2 - typescript

• 编辑时间：2020-09-05
• 执行用时：80ms
• 内存消耗：37.8MB
• 编程语言：typescript
• 解法介绍：[官方题解](https://leetcode-cn.com/problems/permutation-sequence/solution/di-kge-pai-lie-by-leetcode-solution/)。

function getPermutation(n: number, k: number): string {
  const factorials = [1];
  for (let i = 1; i < n; i++) factorials[i] = factorials[i - 1] * i;
  k--;
  let ans = '';
  const valid: number[] = new Array(n + 1).fill(1);
  for (let i = 1; i <= n; i++) {
    let order = ~~(k / factorials[n - i]) + 1;
    for (let j = 1; j <= n; j++) {
      order -= valid[j];
      if (order === 0) {
        ans += j;
        valid[j] = 0;
        break;
      }
    }
    k %= factorials[n - i];
  }
  return ans;
}