LeetCode 60. 排列序列

约 5 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 10-20 字节 微软 美团 快手 猿辅导
标签
数学 递归

题目描述

✅ 60. 排列序列

image-20260928221945600

image-20260928221945601

题意分析

将数字 1..n 的所有排列按字典序排列，返回其中从 1 开始计数的第 k 个。每个数字恰好使用一次，题目保证 1 <= n <= 9 且排名合法。

不需要生成前面所有排列。若能算出一个前缀下有多少种排列，就可以跳过整段候选，逐位确定目标排列。

解法：阶乘分组定位每一位

核心思路

[!blue]

假设已经固定一段前缀，还剩 remain 个未使用的数字。字典序会先比较下一位，所以以最小候选为下一位的排列全部在前，以第二小候选为下一位的排列紧随其后，依此类推。每个候选一旦固定，剩余 remain-1 个数字可以任意排列，因此每块都有 (remain-1)! 种，且这些块连续、等大。

先执行一次 k--，把从 1 开始的排名变成从 0 开始的偏移。令 blockSize = (remain-1)!，那么 k / blockSize 是目标前面完整跳过的块数，也就是当前应选数字在升序候选列表中的下标；k % blockSize 则是进入这一块后，目标在块内的偏移。

选中数字后，把它加入答案并从候选列表删除，剩下的数字仍保持升序。更新为块内偏移后，问题变成“固定了更长前缀，继续寻找剩余数字的指定排列”，因此可以重复相同过程直到选完所有位。

每轮都有 0 <= k < remain!，所以商一定落在 0..remain-1，不会越过候选列表；余数小于 (remain-1)!，恰好维持下一轮的范围。最后只剩一个数字时，块大小为 0! = 1，偏移必为 0，直接取唯一候选即可。

解题步骤

  1. 预处理 factorial[i] = i!，设置 factorial[0] = 1。
  2. 初始化升序候选列表 1..n，并且只在进入循环前执行一次 k--。
  3. 从 remain = n 逐步减到 1，每轮令 blockSize = factorial[remain-1]。
  4. 计算 index = k / blockSize，将对应候选加入答案，并从列表删除，保持其余数字的顺序。
  5. 执行 k %= blockSize，继续在选中块内部定位下一位；所有数字选完后返回答案字符串。

代码实现

class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n + 1];

        factorial[0] = 1;

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

        List<Integer> nums = new ArrayList<>();

        for (int num = 1; num <= n; num++) {
            nums.add(num);
        }

        StringBuilder ans = new StringBuilder();

        // 只在入口转换为零基排名，后续余数已经是块内零基偏移。
        k--;

        for (int remain = n; remain > 0; remain--) {
            int blockSize = factorial[remain - 1];
            // 商决定选择哪个候选，余数决定进入该块后的排名。
            int index = k / blockSize;

            ans.append(nums.remove(index));
            k %= blockSize;
        }

        return ans.toString();
    }
}

func getPermutation(n int, k int) string {
    factorial := make([]int, n+1)
    factorial[0] = 1
    for i := 1; i <= n; i++ {
        factorial[i] = factorial[i-1] * i
    }

    nums := make([]int, n)
    for i := range nums {
        nums[i] = i + 1
    }

    ans := make([]byte, 0, n)
    // 只在入口转换为零基排名，后续余数已经是块内零基偏移。
    k--
    for remain := n; remain > 0; remain-- {
        blockSize := factorial[remain-1]
        // 商决定选择哪个候选，余数决定进入该块后的排名。
        index := k / blockSize
        ans = append(ans, byte('0'+nums[index]))
        nums = append(nums[:index], nums[index+1:]...)
        k %= blockSize
    }
    return string(ans)
}

复杂度分析

  • 时间复杂度：$O(n^2)$。阶乘预处理为 $O(n)$；共选择 $n$ 次，每次商和余数计算为 $O(1)$，但 Java 数组列表或 Go 切片删除元素需要移动后缀，累计为 $O(n^2)$。
  • 空间复杂度：$O(n)$。阶乘表、剩余候选与答案的大小都与 n 同阶。

关键点总结

[!green]

  • 相同前缀下，字典序按下一位分成连续块；每块包含剩余位置的全排列，所以大小是阶乘。
  • k / blockSize 决定选哪个数字，k % blockSize 决定进入该块后继续找哪个排列。
  • 每轮删除已选数字并保持候选升序，才能让列表下标始终对应字典序中的块顺序。
  • 合法排名经整除和取余后仍然合法，最后一位由 0! = 1 自然处理。

易错点总结

[!yellow]

  • 忘记入口处的 k--，会把块末尾的排列划到下一块；每轮重复减一也不对，取余后的偏移已经从 0 开始。
  • 用 factorial[remain] 作为块大小：下一位已经固定，每块只有 remain-1 个位置可排列。
  • 忘记删除选中的数字，后续会重复使用；删除时打乱候选顺序，则商不再对应正确的字典序块。
  • 未设置 factorial[0] = 1，最后一位会出现错误的除数。
  • 题目限制 n <= 9，所以阶乘能放入 int，Go 也能用 byte('0'+num) 拼出单个数字；这段字符转换依赖该范围。

相似题目

题目 难度 关联与区别
46. 全排列 中等 全排列树每个首选分支含有固定阶乘数量的叶子，本题利用这一数量跳过整个分支。
47. 全排列 II 中等 逐位选择未使用元素构造排列；本题用阶乘块大小直接定位第 k 个排列，该题排序后增加同层重复剪枝。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/17635354
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！