目标
给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。
示例 1:
输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。示例 2:
输入: n = 1, k = 1
输出: 1说明:
- 1 <= k <= n <= 10^9
思路
求 1 ~ n 的所有数字按字典序排列后的第 k 个数字。
本来想要参考 386.字典序排数 取第 k 个数字。但是数据范围太大，O(n) 的解法不可行。
题目标签显示的是字典树。想象一棵 10 叉树，根为 0，从第一个孩子 1 开始，如果其子树大小小于剩余的数字个数，直接跳过，访问兄弟节点 2，否则进入下一层，从第一个孩子 10 开始，计算其子树大小，如果小于剩余数字个数，访问兄弟节点 11，否则进入下一层。以此类推。
如何统计子树的大小？可以将当前根节点 l 与兄弟节点 r 一起向下计算，当前层的节点个数 = Math.min(r, n + 1) - 1 - l + 1 即 Math.min(r, n + 1) - l。比如，l == 100, r == 200，计算 100 ~ 200 - 1 的数字个数。注意 r 与 n + 1 取最小值，因为要减 1 所以比较的是 n + 1。
代码
/**
* @date 2025-06-09 8:44
*/
public class FindKthNumber440 {
public int findKthNumber(int n, int k) {
int i = 1;
k--;
while (k > 0) {
int cnt = subTreeNodesCnt(i, n);
if (cnt <= k) {
k -= cnt;
i++;
} else {
k--;
i *= 10;
}
}
return i;
}
public int subTreeNodesCnt(int root, int n) {
int cnt = 0;
long l = root;
long r = root + 1;
while (l <= n) {
cnt += Math.min(r, n + 1) - l;
l *= 10;
r *= 10;
}
return cnt;
}
}
性能
