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

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

13小时前

一、题目解读

牛客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个数
    }
};

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