牛客234288题：用前缀树遍历思想解决字典序第K小问题

一、题目解读

题目要求在字典序排列的1~n数字序列中，快速找到第k个数字。字典序的特殊性使得直接排序会超时，需采用前缀树遍历的数学方法优化时间复杂度至O(log²n)。

二、解题思路

核心采用前缀计数法：

1. 将数字视为前缀树，如"1"为根节点，"10~19"为其子节点

2. 通过计算每个前缀覆盖的数字范围（如前缀"1"覆盖1,10~19,100~199...）

3. 动态调整搜索路径：若k大于当前前缀覆盖范围，则横向移动；否则纵向深入子节点

三、解题步骤

1. 初始化：当前前缀curr=1，k需减1适配0-based计数

2. 范围计算：

3. 路径选择：

• 当steps≤k时横向移动（curr++）

• 否则纵向深入（curr*=10）并减少k计数

四、完整代码实现

class Solution {
  public:
    int findKth(int n, int k) {
        int curr = 1;
        k--; // 初始化为第一个数1

        while (k > 0) {
            long steps = 0;
            long first = curr;
            long last = curr + 1;

            // 计算以curr为前缀的数字个数
            while (first <= n) {
                steps += min((long)n + 1, last) - first;
                first *= 10;
                last *= 10;
            }

            if (steps <= k) {
                // 不在当前前缀子树中
                curr++;
                k -= steps;
            } else {
                // 在当前前缀子树中
                curr *= 10;
                k--;
            }
        }

        return curr;
    }
};

五、总结

该算法巧妙利用字典序的树形特性，通过数学计算替代暴力排序。关键点在于：

• 前缀范围计算的准确性

• 横向/纵向移动的条件判断

• 时间复杂度优化至对数级别