知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 80 - 字典序的第K小数字 ## 题目(LeetCode 440) 给定整数 n 和 k,返回 [1, n] 中字典序第 k 小的数字。 ## 大白话理解 把 1 到 n 的数字想象成一棵十叉树(前缀树),字典序遍历就是前序遍历。关键是能快速计算某个前缀下有多少个数。 ## 解法:前缀树思想 ```java class Solution { public int findKthNumber(int n, int k) { long cur = 1; k--; // cur=1 已经是第 1 个 while (k > 0) { long steps = countSteps(n, cur, cur + 1); if (steps <= k) { // 跳过当前子树 cur++; k -= steps; } else { // 进入当前子树 cur *= 10; k--; } } return (int) cur; } // 计算从 prefix 到 next 之间有多少个 <= n 的数 private long countSteps(int n, long cur, long next) { long steps = 0; while (cur <= n) { steps += Math.min(n + 1, next) - cur; cur *= 10; next *= 10; } return steps; } } ``` ## 复杂度 - 时间 O(log²n),空间 O(1) ## 一句话总结 把数字看成十叉前缀树,计算子树大小来决定是跳过还是深入。 ## 说明 字典序第 K 小数字是一道较难的题,暴力生成所有数字排序需要 O(n log n) 时间和 O(n) 空间,对于大 n 不可行。 当前前缀树解法是最优方案,O(log²n) 时间 O(1) 空间。核心是 `countSteps` 函数能在 O(log n) 时间内计算某个前缀下有多少个合法数字,从而决定是跳过整个子树还是深入。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入