TNotes.leetcode

Appearance

0060. 排列序列【困难】

0060. 排列序列【困难】 ​

1. 📝 题目描述 ​

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

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

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

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

示例 1：

txt
输入：n = 3, k = 3
输出："213"

示例 2：

txt
输入：n = 4, k = 9
输出："2314"

示例 3：

txt
输入：n = 3, k = 1
输出："123"

提示：

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

2. 🎯 s.1 - 阶乘分组 + 贪心 ​

c
char* getPermutation(int n, int k) {
    int numbers[9];
    int factorial[10];
    factorial[0] = 1;

    for (int i = 1; i <= n; i++) {
        numbers[i - 1] = i;
        factorial[i] = factorial[i - 1] * i;
    }

    int rank = k - 1;
    char* result = (char*)malloc(sizeof(char) * (n + 1));

    for (int remaining = n; remaining >= 1; remaining--) {
        int groupSize = factorial[remaining - 1];
        int index = rank / groupSize;

        result[n - remaining] = (char)(numbers[index] + '0');

        for (int i = index; i < remaining - 1; i++) {
            numbers[i] = numbers[i + 1];
        }

        rank %= groupSize;
    }

    result[n] = '\0';
    return result;
}
js
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  const numbers = []
  const factorial = Array(n + 1).fill(1)

  for (let i = 1; i <= n; i++) {
    numbers.push(String(i))
    factorial[i] = factorial[i - 1] * i
  }

  let rank = k - 1
  let result = ''

  for (let remaining = n; remaining >= 1; remaining--) {
    const groupSize = factorial[remaining - 1]
    const index = Math.floor(rank / groupSize)

    result += numbers[index]
    numbers.splice(index, 1)
    rank %= groupSize
  }

  return result
}
py
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        numbers = [str(i) for i in range(1, n + 1)]
        factorial = [1] * (n + 1)

        for i in range(1, n + 1):
            factorial[i] = factorial[i - 1] * i

        rank = k - 1
        result = []

        for remaining in range(n, 0, -1):
            group_size = factorial[remaining - 1]
            index = rank // group_size

            result.append(numbers.pop(index))
            rank %= group_size

        return "".join(result)
  • 时间复杂度：O(n2)，其中 n 是数字个数；一共选出 n 位，每次从候选数组中删除一个数字的代价是 O(n)
  • 空间复杂度：O(n)，需要维护候选数字数组、阶乘数组和答案字符串

算法思路：

  • 核心思想是利用数学规律 => 不用逐一枚举排列，而是直接算出每一位该放什么数字。
  • 对于当前还剩 m 个数字时，以某个固定数字开头的排列一共有 (m - 1)! 个，因此可以把所有排列按首位数字分成若干个大小相同的组
  • 将 k 改成从 0 开始计数后，用当前排名除以 (m - 1)! 的整数部分，就能确定当前位应该选候选数组中的第几个数字
  • 选中该数字后，将它从候选数组中删除；剩余要找的是当前分组内部的第 k % (m - 1)! 个排列
  • 重复这个过程，直到所有位置都被确定，最终拼接出的字符串就是答案

Discussions