【牛客234288题解析】前缀计算与迭代查找第K个数：高效求解不含前导零的序列元素

一、题目解读

牛客234288题要求在一个由1到n的数字组成的序列中，找到第K个不含前导零的数。例如，当n=12时，序列为[1,2,3...12]，若K=5，则答案为5。题目关键在于避免暴力生成所有数字并排序，需设计高效算法直接定位目标元素。

二、解题思路

用户代码采用前缀计算与迭代的方法，核心思想是：

1. 通过计算以当前数字为前缀的子树中数字个数（如“1”前缀包含[1,10]共10个数），判断第K个数是否在该子树内。

2. 若子树包含K，则进入该前缀分支（如curr=1→curr=10）；否则跳过该子树，继续迭代下一个前缀。

3. 利用二进制拆分思想，减少不必要的数字生成，实现O(log n)时间复杂度。

三、解题步骤

1. 初始化：

    curr=1（从第一个数字开始），k--（因后续循环从0开始计数）。

2. 计算前缀子树中的数字个数：

    使用first和last变量模拟前缀扩展（如1→10、12→120等）。

    通过steps += min(n+1, last) - first计算子树大小，避免超出n范围。

3. 判断子树是否包含目标K：

    若steps <= k，说明第K个数不在当前子树，更新curr++（移至下一个前缀）和k -= steps（扣除已跳过数字）。

    若steps > k，说明K在当前子树中，更新curr *= 10（进入子树分支），k--（继续查找子树中的第K个）。

4. 循环终止与结果返回：

当k=0时，当前curr即为第K个数。

四、代码与注释

class Solution {
public:
    int findKth(int n, int k) {
        int curr = 1; // 当前前缀数字
        k--; // 初始化为第一个数1（因循环从0开始计数）
        while (k > 0) {
            long steps = 0; // 当前前缀子树的数字个数
            long first = curr; // 子树起始数字（如1→10的1）
            long last = curr + 1; // 子树结束数字（如1→10的10）
            
            // 计算以curr为前缀的数字个数
            while (first <= n) {
                steps += min((long)n + 1, last) - first; // 避免超出n范围
                first *= 10; // 扩展前缀（如1→10→100）
                last *= 10; // 对应结束位置（如10→100→1000）
            }
            
            if (steps <= k) { // 不在当前子树中
                curr++; // 移至下一个前缀（如1→2）
                k -= steps; // 扣除已跳过的数字
            } else { // 在当前子树中
                curr *= 10; // 进入子树分支（如1→10）
                k--; // 继续查找子树中的第K个
            }
        }
        return curr; // 循环结束时，curr即为第K个数
    }
};

注释说明：代码通过迭代与数学推导，高效定位目标元素，避免生成完整序列。

五、总结

该解法通过前缀计算与迭代，将问题转化为子树查找，巧妙利用二进制拆分思想，大幅降低时间复杂度至O(log n)。关键点在于：

1. 子树数字个数的精确计算（避免溢出与边界问题）。

2. 循环不变量维护：k始终表示剩余需要查找的位数。

3. 前缀扩展的数学推导（如1→10→100）。

在实际应用中，此类算法适用于需要快速定位有序序列中特定元素的场景，尤其当数据量庞大时效果显著。需注意对边界条件（如n+1与min函数）的处理，确保正确性。