LeetCode 440. 字典序的第K小数字
题目描述
题意分析
在整数
1到n中，按照各整数的十进制字符串的字典序排列，返回排在第k个位置的整数。这里比较的是从左到右出现的字符，不是数值大小；一串字符若是另一串的前缀，较短的串排在前面。排名从
1开始，题目保证1 <= k <= n <= 10^9。只需要找到这个排名对应的数，不需要输出全部排序结果。范围很大，不能先生成所有整数再排序。
解法：前缀树计数跳过子树
核心思路
[!blue]
把每个十进制整数看成一个前缀树节点。第一位只能是
1到9，一个前缀的孩子是在末尾追加0到9，并且数值不超过n的那些数。字典序会先访问前缀自身，再按末位从小到大访问它的孩子，所以正好对应这棵树的先序遍历。共享一个前缀的全部整数在字典序中连续出现。若能数出当前前缀
cur的子树大小，就能判断目标是否在这整段里：不在就整段跳过，在就继续向下找。树只用于理解顺序，代码并不实际创建节点。统计子树时，先令
first = cur、next = cur + 1。同一位数下，以该前缀开头的整数恰好落在半开区间[first, next)；多加一位后，两端同时乘十。每层与合法上界截取，贡献为min(n + 1, next) - first，只要first <= n就继续累加。使用n + 1是因为右端不包含在区间内，而整数n应当允许被计入。初始化
cur = 1，再令k--，把排名转换成“从当前节点还需前进多少步”。设子树有steps个节点，它包含cur自身。若steps <= k，目标在这段之后，移动到cur + 1并扣掉steps；若steps > k，目标仍在这段内部，而k > 0说明不是当前节点，于是进入最小孩子cur * 10，只扣掉访问当前节点的一步。一旦进入某个前缀，已经确认目标在它的子树里，所以后续只需在其孩子之间横移或继续下探，不必回溯跳出该前缀。
k减至零时，当前节点就是目标。计数边界不断乘十，可能超过n，因此使用 64 位整数保存前缀和边界。
解题步骤
- 令
cur = 1，将k减一；若已经为零，直接得到答案。- 用
countSteps逐层累加当前前缀覆盖的合法整数数量，包括前缀自身。- 若
steps <= k，令cur++、k -= steps，跳过整段。- 否则令
cur *= 10、k--，进入当前前缀下的第一个孩子。- 重复直到剩余步数为零，返回
cur。
代码实现
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)$，每层至多横移经过十个兄弟中的常数个，再进入下一层；每次子树计数还需要向下检查 $O(\log n)$ 层。
- 空间复杂度：$O(1)$，只保存当前前缀、剩余步数和计数边界，没有实际建树或保存遍历序列。
关键点总结
[!green]
- 字典序对应前缀树先序，共享前缀的子树是一段连续排名。
- 子树计数包含当前节点，横移扣整段大小，下探只扣当前节点的一步。
k始终表示从当前节点还需前进的步数，归零才能返回。
易错点总结
[!yellow]
- 忘记初始
k--，会把当前已经位于第一项的状态又算成一次待前进的位置。- 跳过子树时只扣一，或进入孩子时扣整棵子树，会破坏剩余排名。
- 判断写成
steps < k，会在目标恰好位于下一兄弟时错误地下探；相等时也应整段跳过。- 使用
min(n, next)会漏算合法端点n；半开区间应截到n + 1。- 计数循环必须允许
first == n，这一层仍有一个合法整数。- 层级边界使用 32 位整数，在接近上界后继续乘十可能溢出，导致计数和终止条件出错。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 386. 字典序排数 | 中等 | 本题利用数字前缀子树大小跳过整块，原题按字典序逐个输出全部数字。 |
| 60. 排列序列 | 困难 | 同样按每个前缀分支包含的方案数跳到第k项，排列题用阶乘，本题用十进制前缀范围计数。 |