面试题44：数字序列中某一位的数字

从“不生成无限字符串”开始

先预测：把非负整数连续写成 0123456789101112…。索引0是0，索引9是9，索引10已经进入数字10的首字符1。若要查索引一百万，没有必要真的拼接前一百万个字符；它必然落在某个固定数字长度的区间里。

题目“数字序列中某一位的数字”使用。作者先按“一位数、两位数、三位数”分组，执行“跳过整段位数区间”，再在目标块中“定位具体数字和具体位”。

位数块的数量与字符长度

一位数包括0到9，共10个数字；这是作者模型与旧页最关键的差异。从两位数开始，d位正整数从10的d减1次幂到10的d次幂减1，共9乘10的d减1次幂个。

每个数字贡献d个字符，所以一个包含的字符数为：

一位数块占索引0到9共10位；两位数块占接下来的180位，即全局索引10到189；三位数块从190开始，占2700位。边界判断必须用“剩余index严格小于块长”，等于块长说明恰好落在下一块首位。

先跳过整块

作者从digits等于1开始。若index不在当前块，减去 numbers * digits 并把digits加1；进入目标块后，index不再是全局位置，而是该块首字符起算的。

int countOfIntegers(int digits) {
    if (digits == 1) {
        return 10;
    }
    const int count =
        static_cast<int>(
            std::pow(10, digits - 1));
    return 9 * count;
}
 
int beginNumber(int digits) {
    if (digits == 1) {
        return 0;
    }
    return static_cast<int>(
        std::pow(10, digits - 1));
}
 
int digitAtIndex(int index) {
    if (index < 0) {
        return -1;
    }
 
    int digits = 1;
    while (true) {
        const int numbers =
            countOfIntegers(digits);
        if (index < numbers * digits) {
            return digitAtIndex(
                index, digits);
        }
 
        index -= digits * numbers;
        ++digits;
    }
}

例如索引1000先减一位数块10，得到990；再减两位数块180，得到三位数块内偏移810。整个过程只遍历位数种类，不遍历具体数字。

用商定位数字、余数定位字符

当前块起始数字记为S，块内偏移记为r，数字长度为d。每个数字占d位，因此整除给出这是块内第几个数字，取模给出该数字内从左起第几个字符：

对r等于810、d等于3、S等于100，目标数字是370，数内偏移0，对应字符3。r等于811和812时整除商仍是270，目标仍是370，只是数内偏移变成1和2。

这个不会因同一数字内的不同字符变化；只有当r跨过d的整数倍时才进入下一个数字。

作者（边界条件）从右侧做整数除法

数内偏移是左侧0基下标。作者把它转换成从右数第几位：indexFromRight = digits - index % digits，然后除以10共indexFromRight减1次，最后取模10。

这里的若为0，就除10的d减1次取最高位；若为d减1，就不除直接取个位。

int digitAtIndex(int index, int digits) {
    int number =
        beginNumber(digits) + index / digits;
    const int indexFromRight =
        digits - index % digits;
 
    for (int i = 1;
         i < indexFromRight; ++i) {
        number /= 10;
    }
    return number % 10;
}

作者不用to_string取字符，完全以整数运算定位。两种写法都可行，但字符串版应明确编码和负号，本题数字均非负且每个十进制字符一字节，整数版契约更直接。

189与190为何是关键边界

一位数块10位，两位数块180位，累计190位覆盖全局索引0到189。索引189减去10后块内偏移179，数字序号是89，起始10加89得到99，数内偏移1，结果是末位9。

索引190先减10得到180；它不严格小于两位数块长度180，因此还要完整减掉两位数块，进入三位数块偏移0。起始数字100，数内偏移0，结果为首位1。

1000到1002连续定位370

索引1000扣除前两块后为810。810整除3是270，所以数字是100加270，即370；余数0取3。索引1001、1002的商仍是270，余数依次1、2，分别取7和0。

连续三个测试同时证明两层映射：商在同一数字的三个字符间不变，余数按0、1、2移动；下一索引1003才会把商推进到271，对应数字371首位3。

若错误使用1基偏移或先减1，三个结果会整体错位。作者的全局索引、块内偏移和数内偏移始终都是0基，无需额外n减1。

正确性证明

所有非负整数按十进制位数形成互不重叠、顺序连续的块。外层每次减去一个完整块长度，因此不跳过目标字符，也不会重复计数；首次满足剩余偏移小于当前块长时，目标唯一落在该块。

块内每d个字符对应一个数字，欧几里得除法把r唯一写成商乘d加余数，其中余数范围是0到d减1。商唯一确定目标数字，余数唯一确定数内字符。最后按10的幂右移并取个位，得到该位置十进制数字。

三个步骤都是双射式定位：块前缀长度、数字序号、字符序号合起来能恢复原全局索引。因此算法既不会返回另一位置，也不会漏掉任何非负索引。

复杂度与作者实现边界

目标数字有d位时，外层检查d个块，最终取位最多除10共d减1次，时间O(d)，也就是O(log index)；额外空间O(1)。作者使用int，理论无限序列并不等于实现支持任意大索引。

numbers * digits、累计减法与10的幂都可能超出int。std::pow返回double后再转int，大位数还会遇到舍入或越界；源码也没有显式包含标准头 cmath，依赖间接声明不具可移植性。工程版应使用整数位权递推与宽类型。

下面接口接受非负int64索引；对这个输入域，uint64足以容纳所需块计算。负索引返回nullopt，不再占用数字-1做哨兵。

#include <cstdint>
#include <optional>
 
std::optional<int> digitAt(
    std::int64_t signedIndex) {
    if (signedIndex < 0) {
        return std::nullopt;
    }
 
    std::uint64_t index =
        static_cast<std::uint64_t>(signedIndex);
    std::uint64_t digits = 1;
    std::uint64_t start = 0;
    std::uint64_t count = 10;
 
    while (true) {
        const std::uint64_t block =
            count * digits;
        if (index < block) {
            break;
        }
        index -= block;
        ++digits;
 
        if (digits == 2) {
            start = 10;
        } else {
            start *= 10;
        }
        count = 9 * start;
    }
 
    std::uint64_t number =
        start + index / digits;
    const std::uint64_t inside =
        index % digits;
    std::uint64_t shifts =
        digits - 1 - inside;
    while (shifts-- > 0) {
        number /= 10;
    }
    return static_cast<int>(number % 10);
}

若接口扩展到完整uint64索引，count * digits可能在19位块溢出，要用检查乘法或更宽中间类型。宽输入并不自动保证宽中间结果，边界证明必须与公开输入域一致。

作者九组测试的准确语义

作者直接比较 digitAtIndex(inputIndex) 与期望：

1. 索引0、1、9分别返回0、1、9，覆盖一位数块。
2. 索引10返回1，是数字10的首位。
3. 索引189返回9，是数字99的末位。
4. 索引190返回1，是数字100的首位。
5. 索引1000、1001、1002分别返回3、7、0，对应数字370三位。

源码没有负索引测试，尽管函数定义返回-1；也没有11到188的两位数内部样本、1003、三位块末尾2889、四位块起点2890或大索引溢出测试。

朴素参考可不断把整数转字符串并拼接到超过目标索引，用于短范围差分。边界测试应对每个位数块起点前一位、起点和起点后一位成组三测，最容易发现严格小于、起始数字和0基偏移错误。

#include <cassert>
#include <string>
 
int bruteDigit(std::size_t index) {
    std::string sequence;
    for (std::size_t value = 0;
         sequence.size() <= index; ++value) {
        sequence += std::to_string(value);
    }
    return sequence[index] - '0';
}
 
void testDigitsInSequence() {
    for (std::int64_t index = 0;
         index <= 5000; ++index) {
        assert(digitAt(index).value() ==
               bruteDigit(index));
    }
    assert(!digitAt(-1).has_value());
    assert(digitAt(189).value() == 9);
    assert(digitAt(190).value() == 1);
    assert(digitAt(1000).value() == 3);
    assert(digitAt(1001).value() == 7);
    assert(digitAt(1002).value() == 0);
}

朴素字符串会占O(index)内存，只适合测试小索引。生产算法的优势正是不会生成此前字符，测试参考不应被误用为线上实现。

序列定义改变时怎样迁移

若序列从1而不是0开始，一位数块只有9项，所有后续全局索引比作者模型左移1；不能只改beginNumber而不改count和测试。若索引改成1基，入口应先统一转换一次，内部仍保持0基，避免每层散落减1。

若连接的是偶数、质数或固定进制表示，位数块数量公式会改变，但“跳整块、商定位对象、余数定位对象内部位置”的框架仍可复用。二进制或十六进制还要定义字符表和大小写。

若数字之间插入逗号，分隔符也是序列字符，固定d字符一组的映射失效。可把每项长度改为数字位数加分隔符长度，并单独处理最后一项是否带分隔符。

面向超长十进制索引时，连index本身都可能是大整数；可用十进制字符串做块长比较和减法，再把落入目标块后的商余数转成可管理范围。这与作者int接口是不同问题，应明确扩展边界。

本章练习

本章回顾

1. 作者序列从字符0开始，索引与所有内部偏移均为0基。
2. 一位数块有10个数字；d位块从两位起有9乘10的d减1次幂个数字。
3. 先减去完整块字符数，直到剩余偏移落入当前块。
4. 块内偏移整除d定位目标数字，取模d定位数内字符。
5. 作者从右侧反复除10，再取个位得到目标数字。
6. 索引189是99末位，190是100首位，严格边界不能混淆。
7. 索引1000到1002依次命中370的3、7、0。
8. 算法O(log index)、O(1)，但作者int与pow实现需防溢出和转换。

名词解释