C++实现自然数拼接字符串第k位查找的输出错误排查

核心bug定位 #

你的代码问题出在计算目标自然数的行：

ans += (k - 1) / digit - 1;

这里多了不必要的-1操作，导致最终找到的自然数比实际需要的小1，对应取到的字符也出错。

错误原因解释 #

• 前面的循环已经把k对齐到了digit位数分组的起始偏移，digit位数的第一个自然数是10^(digit-1)（也就是你初始化的ans变量的值）
• 第m个digit位自然数对应的就是ans + m，其中m的计算规则就是(k-1)/digit，不需要额外减1

错误验证 #

以测试输入k=7为例：

1. 原代码计算得到ans = 1 + (7-1)/1 -1 = 6，取到的字符是6，和预期7不符
2. 去掉-1后计算得到ans = 1 + (7-1)/1 =7，取到的字符是7，符合预期
   以测试输入k=19为例：
3. 原代码对齐后k=10，digit=2，计算得到ans=10 + (10-1)/2 -1 = 13，取到的字符是3，和预期4不符
4. 去掉-1后计算得到ans=10 + (10-1)/2 =14，取到的字符是4，符合预期

修正后完整代码 #

#include <iostream>

int main() {
    using std::cin;
    using std::cout;
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int64_t k;
        cin >> k;
        int64_t aux = 9;
        int digit = 1;
        while (k > aux * digit) {
            k -= aux * digit;
            aux *= 10;
            digit++;
        }
        int64_t ans = 1;
        for (int i = 0; i < digit - 1; i++) {
            ans *= 10;
        }
        // 去掉了多余的-1
        ans += (k - 1) / digit;
        k -= (k - 1) / digit * digit;
        int64_t helper = 1;
        for (int i = 0; i < digit - k; i++) {
            helper *= 10;
        }
        cout << ans / helper % 10 << '\n';
    }
    return 0;
}

修正后测试输入的三个用例输出完全符合预期。

内容的提问来源于stack exchange，提问作者carcinogenic game