1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public int findKthNumber(int n, int k) {
            int cur = 1;// 从字典序第一个数字 1 开始
            k--;// 转换为 0 索引
            while (k > 0) {

                // 计算以cur为根的子树，包含的有效节点数量

                int steps = getSteps(cur, n);

                if (steps <= k) {
                    // 目标不在当前子树，跳过整棵子树，更新k和当前节点
                    k -= steps;
                    cur++;
                } else {
                    // 目标在子树中，进入子节点，k减1（跳过当前节点）
                    cur *= 10;
                    k--;
                }
            }

            return cur;
        }

        // 计算以cur为根节点的子树中，<=n的节点总数
        private int getSteps(int cur, long n) {
            int steps = 0;
            long first = cur; // 当前层起始节点
            long last = cur; // 当前层结束节点

            while (first <= n) {
                // 累加当前层的节点数，防止last超出n
                steps += Math.min(last, n) - first + 1;

                // 进入下一层
                first *= 10;
                last = last * 10 + 9;
            }

            return steps;
        }