LeetCode 440. 字典序的第K小数字

2026-08-10 HGNULB 约 6 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 440. 字典序的第K小数字

题意分析

给定两个整数 n 和 k，在 1 到 n 这 n 个整数里，按字典序从小到大排好之后，返回排在第 k 位的那个数。

第一个必须抠清楚的点是「字典序」不是「数值序」。字典序是把整数当成字符串逐字符比较的：1 < 10 < 11 < 12 < 13 < 2 < 3 < …，所以 2 排在 13 后面，10 紧跟在 1 后面。凡是把题意读成「第 k 小的数」的，答案会全错。

第二个信号来自数据范围：n 最大可以到 $10^9$，而 k 保证不超过 n。$10^9$ 个数既装不进内存，也不允许我们真的生成出来再排序，甚至连「从头到尾一个一个数过去」的 $O(n)$ 遍历都过不了。题目给出这样的量级，等价于明说：只接受与 n 的位数相关的解法。

边界上要留意几处：k 从 1 开始计数，不是从 0；n = 1 时唯一的答案就是 1；答案本身一定落在 [1, n] 内，可以用 int 返回，但中间的计数过程未必安全。

解法：前缀树计数跳过子树

核心思路

问题关键：n 可达 $10^9$，不能生成并排序 1..n。需要在不枚举所有数字的前提下，直接跳到字典序第 k 个位置。

为什么建模为十叉前缀树：字典序就是前缀树的先序遍历。前缀 p 的孩子依次为 p0, p1, ..., p9；从 1 开始的遍历顺序是 1, 10, 100, ..., 11, ..., 2, ...。因此，只要知道某个前缀子树有多少个合法数字，就能一次跳过整棵子树。

前缀 p 与下一个前缀 p + 1 在各层形成左闭右开区间：

第一层：[p, p + 1)；

下一层：[10p, 10(p + 1))；

再下一层继续同时乘 10。

每层在 1..n 内的节点数为 min(n + 1, next) - first，逐层累加就是该前缀的子树大小。

循环不变量：cur 是当前访问的数字，k 是从 cur 还需向后走的步数。初始 cur = 1 已占第一个位置，所以先执行 k--。设当前子树大小为 steps：

steps <= k：答案不在当前子树，执行 cur++、k -= steps，整体跳到下一个兄弟；

steps > k：答案在当前子树，执行 cur *= 10、k--，进入先序遍历的第一个孩子。

正确性：同一前缀的所有数字在字典序中连续出现，countSteps 又精确统计了这段连续区间的长度，所以比较 steps 与 k 能正确决定“跳过”还是“深入”。两种操作都按实际跨过的节点数更新 k，保持不变量；当 k = 0 时，cur 正是目标数字。

解题步骤

初始化 cur = 1，并把 1 基的 k 减一，改成还需前进的步数。

用 countSteps 逐层统计 [first, next) 与 [1, n + 1) 的交集长度；边界变量必须使用 64 位。

若当前子树大小不超过剩余步数，跳到兄弟并扣除整棵子树；否则进入最左孩子并只扣当前节点。

k 归零时返回 cur。

面试口述示例：n = 13, k = 6 的字典序开头是 1,10,11,12,13,2。以 1 为前缀的子树共有 5 个节点；初始减一后 k = 5，满足 steps <= k，整棵子树被跳过，cur = 2、k = 0，答案就是 2。

边界反例：k = 1 时减一后直接返回 1；当 n = 10 时，计数循环必须包含 first == n 的那一层，否则会漏掉数字 10。

代码实现

class Solution {
    public int findKthNumber(int n, int k) {
        long cur = 1;
        k--;

        while (k > 0) {
            long steps = countSteps(n, cur, cur + 1);
            if (steps <= k) {
                cur++;
                k -= steps;
            } else {
                cur *= 10;
                k--;
            }
        }
        return (int) cur;
    }

    private long countSteps(int n, long first, long next) {
        long steps = 0;
        while (first <= n) {
            steps += Math.min((long) n + 1, next) - first;
            first *= 10;
            next *= 10;
        }
        return steps;
    }
}

func findKthNumber(n int, k int) int {
    cur := int64(1)
    k--

    for k > 0 {
        steps := countPrefixSteps(n, cur, cur+1)
        if steps <= int64(k) {
            cur++
            k -= int(steps)
        } else {
            cur *= 10
            k--
        }
    }
    return int(cur)
}

func countPrefixSteps(n int, first int64, next int64) int64 {
    limit := int64(n) + 1
    steps := int64(0)
    for first <= int64(n) {
        if next < limit {
            steps += next - first
        } else {
            steps += limit - first
        }
        first *= 10
        next *= 10
    }
    return steps
}

复杂度分析

时间复杂度：$O(\log^2 n)$。前缀树深度为 $O(\log n)$，主循环在每层至多跨过常数个十进制兄弟；每次 countSteps 又向下统计 $O(\log n)$ 层。

空间复杂度：$O(1)$，只维护当前前缀、区间边界和计数，没有真正建树。

关键点总结

把字典序识别为十叉前缀树的先序遍历，是从“排序”转向“计数跳步”的关键。

[first, next) 逐层乘 10 可以统一统计前缀子树；用 n + 1 作为右开上界，避免末端少算一个节点。

跳兄弟扣 steps，进孩子只扣 1；先写清 k 表示“剩余步数”就不容易混淆。

first、next 会乘到 $10^{10}$，Java 必须用 long，Go 必须用 int64。

易错点总结

忘记初始 k--：n = 13, k = 1 会多走一步，无法返回 1。

跳过子树时只做 k--，或深入孩子时做 k -= steps：两种分支跨过的节点数正好写反。

条件写成 steps < k：当 steps == k 时本应正好跳到兄弟，却会错误深入子树。

用 min(n, next) 而不是 min(n + 1, next)：右开区间会漏算数字 n。

用 int 保存层级边界：接近 $10^9$ 时继续乘 10 会溢出，可能得到负计数或死循环。

相似题目

题目	难度	考察点
386. 字典序排数	中等	同一棵十叉树，但要求完整先序输出而非定位
60. 排列序列	困难	用阶乘计数在排列树上跳步，逐位确定答案
233. 数字 1 的个数	困难	按位统计数位出现次数，计数而不枚举
378. 有序矩阵中第 K 小的元素	中等	对答案二分，用「不超过 mid 的个数」定位第 k
668. 乘法表中第k小的数	困难	值域二分配合逐行计数，处理巨大隐式表格