LeetCode 60. 排列序列

2026-03-13 HGNULB 约 5 分钟

文章信息 10 个分类 2 个标签

分类

LeetCode CodeTop 困难未解决 10-20 字节跳动微软美团快手猿辅导

题目描述

✅ 60. 排列序列

题意分析

把 1 到 n 这 n 个互不相同的数字排成一列，一共有 n! 种排法。把这些排列按字典序从小到大编号，要求返回第 k 个排列对应的字符串。

两个约束信号非常关键。第一，1 <= n <= 9，所以最多只有 9! = 362880 个排列，k 用 int 存放绰绰有余，而且每个数字都是一位十进制字符，可以直接拼成字符串。第二，题目只要第 k 个，不要前 k 个，也不要全部——只问单个结果的题，往往意味着存在不需要枚举全体的直接构造方式。

还要注意编号的起点：题目里的 k 从 1 开始计数，第 1 个排列是 123...n；而数组下标、以及后面要用到的「分组编号」都从 0 开始。这个 1 基和 0 基的差异是本题最容易翻车的地方。

边界情况包括：k = 1 时应返回最小排列 123...n；k = n! 时应返回最大排列 n...321；n = 1 时无论如何只有一个排列 "1"。

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

核心思路

若用回溯生成前 k 个排列，最坏要枚举 $n!$ 个结果；但字典序中的排列天然按阶乘大小分块，可以直接定位每一位。

假设当前还有 remain 个数字可选。固定第一位后，剩余数字有 $(remain-1)!$ 种排列，因此每个候选数字对应一个大小相同、连续的字典序区间。把题目的 1 基排名先转成 0 基偏移 k--，就可以计算：

index = k / (remain - 1)!：目标落在第几个区间，即当前位选剩余数字中的第 index 个；

k = k % (remain - 1)!：目标在该区间内的新偏移。

选中数字后将它从升序候选列表删除，继续处理下一位。这就是阶乘数系（逆康托展开）：从高位到低位依次用阶乘作权值，直接把排名还原为排列。

循环不变量是：每轮开始时，候选列表按升序保存所有未使用数字，k 是目标在这些数字全部排列中的 0 基排名。除法确定当前块，取余保留块内排名，因此进入下一轮后不变量仍成立。

解题步骤

预处理 factorial[i] = i!，其中 factorial[0] = 1。

初始化升序候选列表 [1, 2, ..., n]，并执行 k--。

当还剩 remain 个数字时，令块大小为 factorial[remain - 1]。

用 k / blockSize 找到当前位的候选下标，取出并删除该数字。

用 k %= blockSize 更新块内排名，继续下一位。

以 n = 4, k = 9 为例：0 基偏移为 8。首位每块有 3! = 6 个排列，8 / 6 = 1，选第 2 个候选数字 2，块内偏移为 2；下一位每块有 2! = 2 个排列，2 / 2 = 1，选 3，偏移归零；剩余数字依次为 1、4，答案是 2314。

代码实现

import java.util.ArrayList;
import java.util.List;

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)$，但数组列表删除元素要移动后缀，累计为 $O(n^2)$；在题目 n <= 9 的范围内这是最直接的实现。

空间复杂度：$O(n)$。阶乘表、候选列表和答案都与 n 同阶。

关键点总结

字典序按首位分成等大的连续块，每块大小是剩余数字个数的阶乘。

必须先将 k 从 1 基排名转成 0 基偏移，之后才能统一使用整除和取余。

候选数字必须保持升序；块下标才等于当前应选数字的下标。

每轮先用商选数字，再用余数进入该块，二者分别回答「选谁」和「块内排第几」。

面试若追问更大规模，可用支持第 k 小查询与删除的数据结构将选择降到 $O(\log n)$；本题 n <= 9，没有必要增加复杂度。

易错点总结

忘记 k--：当 k 恰好等于块大小时会错误地落到下一块，例如 n = 3, k = 2 应得到 132。

阶乘下标写成 factorial[remain]：当前位固定后只有 remain - 1 个位置可排列，块大小应为 (remain - 1)!。

选中数字后没有从候选列表删除，会在后续位置重复使用同一个数字。

候选列表不是升序，index 对应的块次序就不再是字典序。

Go 中直接用 byte('0' + num) 依赖 n <= 9；若数字可能超过 9，应改用整数转字符串。

相似题目

题目	难度	考察点
31. 下一个排列	中等	原地求字典序的下一个排列
46. 全排列	中等	回溯枚举无重复元素的全排列
47. 全排列 II	中等	排序后同层去重剪枝
784. 字母大小写全排列	中等	每位二选一的枚举
LCR 083. 全排列	中等	46 题的同题异名版本
LCR 084. 全排列 II	中等	47 题的同题异名版本
剑指 Offer 38. 字符串的排列	中等	字符集上的排列去重
面试题 08.07. 无重复字符串的排列组合	中等	字符互异时的排列生成
面试题 08.08. 有重复字符串的排列组合	中等	字符重复时的计数去重