日期: 2025 年 6 月 9 日

目标

给定整数 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;
    }
}

性能