摘要

这道题乍一看像是要把 1 到 n 排序后找第 k 小的数字，但 n 最大能到 10⁹，如果你真把所有数字转字符串排个序，那内存瞬间爆炸。
其实它考的不是排序，而是一个非常巧妙的 按字典序遍历前缀树（Trie-like 结构） 的技巧：不需要真的生成树，只需要能算出每个前缀下面有多少数字，就能一步步往下走，找到第 k 个位置的数字。

描述

题目要求你在 1 到 n 之间，按照“字符串字典序”的排序方式，找到第 k 小的数字。例如：

对于 n = 13：

字典序排列：

1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9

所以 k=2 时答案是 10。
你会发现字典序不是按数字大小排，而是按“字符串从左到右”排序的方式来排。

因为 n 可以到 10⁹，我们不能直接生成数组。必须找到一条“逻辑路径”，让我们能够模拟字典序，而不生成完整序列。

题解答案

关键思路：
把 1 ~ n 看成挂在一个“字典序前缀树”上的节点，例如：

1
 ├── 10
 │    ├── 100
 │    ├── 101
 │    ...
 ├── 11
 ├── 12
2
3
...

我们要找第 k 小，就是在这棵树上进行类似 DFS 的“前序遍历”，但不是真的遍历，而是每次通过计数跳过一个整个子树。

核心操作是：
给定前缀 prefix，我们可以算出在区间 [prefix, prefix+1) 之间有多少数字 <= n。
例如前缀 1，它下有：

1, 10, 11, 12, 13

五个数字。

如果想找第 k 小的数字：

1. 从 prefix = 1 开始；
2. 看 prefix 下面一整个子树有多少数字 count；
3. 如果 k > count，则说明第 k 个数字不在 prefix 这一支里，我们跳到下一个 prefix（也就是 prefix+1），并将 k -= count；
4. 如果 k <= count，则说明目标在 prefix 这一支里，我们往下走（prefix *= 10），并将 k -= 1，因为 prefix 本身是该子树第一个数字；
5. 重复直到 k==0；

这种方式堪称暴力排序的完全替代方案，同时效率极高。

可运行 Swift 实现

下面的代码可直接在 Xcode Playground 或 Swift 文件里运行：

import Foundation

class Solution {
    func findKthNumber(_ n: Int, _ k: Int) -> Int {
        var k = k - 1  // 因为我们把 prefix 本身当成第一个节点
        var prefix = 1

        while k > 0 {
            let count = countPrefix(n, prefix, prefix + 1)
            if k >= count {
                // 不在这一支，跳到下一个前缀兄弟节点
                k -= count
                prefix += 1
            } else {
                // 在这一支，往下走
                prefix *= 10
                k -= 1
            }
        }

        return prefix
    }

    // 计算区间 [prefix, nextPrefix) 中的数字数量（<= n）
    private func countPrefix(_ n: Int, _ prefix: Int, _ nextPrefix: Int) -> Int {
        var curr = prefix
        var next = nextPrefix
        var count = 0

        while curr <= n {
            count += min(n + 1, next) - curr
            curr *= 10
            next *= 10
        }
        return count
    }
}

// Demo 测试
let solution = Solution()

let tests = [
    (13, 2),
    (100, 10),
    (1_000_000_000, 100000),
    (1, 1),
    (5000, 150)
]

for (n, k) in tests {
    print("n=\(n), k=\(k) → \(solution.findKthNumber(n, k))")
}

题解代码分析

我们逐步拆解代码中最关键的几个点。

1. 为什么要 k -= 1？

因为我们把当前 prefix 当作该前缀子树的第一个节点。例如 prefix=1：

字典序顺序：

1, 10, 11, 12, 13, ...

所以当你决定往 prefix 的子树里继续往下走时，需要把 1 的位置算进去，于是 k -= 1。

2. countPrefix 是整个题目的灵魂

它计算：

[prefix, nextPrefix) 这个前缀区间内，有多少数字 <= n。

不断扩大区间：

[prefix, nextPrefix)
[prefix*10, nextPrefix*10)
[prefix*100, nextPrefix*100)
...

直到超过 n。

例如 n = 13，prefix = 1，nextPrefix = 2：

curr=1, next=2: min(14,2)-1 = 1
curr=10, next=20: min(14,20)-10 = 4
curr=100 > 13 stop
总计 = 5

也就是 1, 10, 11, 12, 13 共 5 个数字。

3. 核心循环为什么这么高效？

因为每次不是“一个数字一个数字地走”，而是按“整个子树数量”跳：

• 如果 k 比子树大 → 一步跳过这整个分支；
• 如果在子树里 → 直接深入下一层分支；

这让时间复杂度变成 O(log n)，非常高效。

示例测试及结果

在 Demo 中我们测试了几组：

例如：

n = 13, k = 2

输出：

10

再例如：

n = 100, k = 10

字典序前十个分别是：

1, 10, 100, 11, 12, 13, 14, 15, 16, 17 ...

第 10 个是 17。

再大一点测试：

n = 1_000_000_000, k = 100000

这种规模如果你用排序法绝对挂掉，但前缀跳跃法是几毫秒级别即可算出。

时间复杂度

每次跳层计算数量的过程是按十倍增长，最多进行 log₁₀(n) 次。

外层循环最多也执行 log₁₀(n) 次。

总的时间复杂度：

O(log² n)
在 n=1e9 这种规模下非常快。

空间复杂度

只使用若干整数变量，栈内不存储大量数据：

O(1)。

总结

这道 LeetCode 440 是一道典型的“字典序前缀树”思维题，看似困难，但理解后你会发现：

1. 我们不是在排序数字，而是在“跳过”子树。
2. 关键是能计算某个前缀下有多少数字。
3. 利用这个计数，就能快速找到第 k 个数字。

这类题在某些数据结构、分布式系统的“范围扫描”“前缀计数”“分页”中其实很有用：
你不需要把所有节点都展开，只要能计算“前缀区间的数量”，就能精确跳到需要的位置。