LeetCode 剑指 Offer 44. 数字序列中某一位的数字
目录
题目描述
题意分析
把 0、1、2、3……这些整数按顺序首尾相接写成一条无限长的字符串「0123456789101112…」，给定下标 n，返回这条串上第 n 位是哪个数字（返回 0 到 9 的整数，而不是字符）。
这里的下标是从 0 开始数的：第 0 位是 0，第 9 位是 9，第 10 位是 10 的十位「1」，第 11 位是 10 的个位「0」。
n 的上界是 $2^{31} - 1$，接近 21 亿。这条约束说明连「把序列拼出来」都不可能，甚至不能逐个数字地累加长度——21 亿个字符对应的数字个数虽只有两亿多，但仍然太慢。可行的复杂度只能是 $O(\log n)$ 级别，也就是说要按「位数」整块跳过。
边界有三处：n 小于 10 时答案就是 n 自身；跨区间时会出现极大的中间量（9 位数区间的字符总数是 81 亿），必须用 64 位整数；把「第几个字符」换算成「第几个数」时是否减一，直接决定答案会不会整体偏移一位。
解法：分段定位
核心思路
朴素做法是从 0 开始逐个数，把每个数的位数累加起来，直到累计长度超过 n。这个思路方向是对的，但粒度太细：n 接近 21 亿时要循环两亿多次，超时是必然的。
瓶颈在于「一个数一个数地扣」。观察这条序列的结构会发现，它天然按位数分成若干整块：1 位数是 0 到 9，2 位数是 10 到 99，3 位数是 100 到 999，第 d 块的起始数字是 $10^{d-1}$，共有 $9 \times 10^{d-1}$ 个数，贡献 $9 \times 10^{d-1} \times d$ 个字符。既然一整块的字符数有闭式公式，就可以整块整块地扣，而块的个数只有十个左右——这就把线性降成了对数。
把 0 单独拿出来处理会让公式更整齐：约定 n < 10 时直接返回 n，之后从「1 位正整数区间共 9 个字符」开始扣。此时把 idx 理解成「在当前区间内的第几个字符，从 1 开始计数」，正整数区间的起点 start 与位数 digit 一一对应。
由此得到循环维护的不变量：在每轮循环开始时，目标字符位于「起始数字为 start 的 digit 位数区间及其之后」，且 idx 表示它在这段后缀里的序号（从 1 开始），count 是当前区间的字符总数。若
idx > count，说明目标不在本区间，扣掉 count 并推进到下一区间，不变量仍成立；否则目标就落在本区间内，循环结束。定位落地时用两个除法：
(idx - 1) / digit是目标数字相对 start 的偏移，(idx - 1) % digit是它在这个数字内部的第几位。减一是因为 idx 从 1 计数而除法的商从 0 计数，两者必须对齐。
解题步骤
- 先处理
n < 10，直接返回 n。这一步把只有 10 个数、每个数贡献 1 个字符的「0 到 9」段单独摘出去，后面的区间公式 $9 \times start \times digit$ 就只对正整数成立，不必再为 0 打补丁。- 把 n 装进 64 位变量 idx，并初始化 digit = 1、start = 1、count = 9。此时 idx 的含义已经从「全局下标」切换成「1 位正整数区间起点开始的第几个字符」，因为前面的 10 个字符（0 到 9）恰好把下标 0 到 9 用掉，而 n ≥ 10 时 idx = n 正好等于在后缀里从 1 开始的序号。
- 当
idx > count时扣掉整块：idx -= count，digit++，start *= 10，count = 9 * start * digit。四个更新必须一起做，顺序也不能乱——count 依赖更新后的 start 和 digit。- 循环退出时目标落在当前区间。用
num = start + (idx - 1) / digit求出具体是哪个数，用offset = (idx - 1) % digit求出在这个数里的第几位。- 把 num 转成字符串取第 offset 个字符，减去
'0'得到数值返回。这里转字符串是 $O(\text{digit})$ 即最多 10 步的常数级操作，不影响整体复杂度。以
n = 1000走一遍：n 不小于 10，idx = 1000，digit = 1，start = 1，count = 9。第一轮 1000 > 9，扣掉 9 得 idx = 991；digit = 2，start = 10，count = 9 × 10 × 2 = 180。第二轮 991 > 180，扣掉得 idx = 811；digit = 3，start = 100，count = 9 × 100 × 3 = 2700。第三轮 811 不大于 2700，循环结束，说明目标落在三位数区间里。
计算
num = 100 + (811 - 1) / 3 = 100 + 270 = 370，offset = (811 - 1) % 3 = 0。把 370 转成字符串取第 0 位是'3'，返回 3。手工验证一下：0 到 9 占了下标 0 到 9 共 10 个字符，10 到 99 占了 180 个字符即下标 10 到 189，从下标 190 开始是 100。第 1000 位相对 190 的偏移是 810，810 / 3 = 270 说明跨过了 270 个完整的三位数，即数字 370，810 % 3 = 0 说明取它的最高位 3，与代码结果一致。
再验证一个小用例
n = 11：idx = 11 > 9，扣成 idx = 2，digit = 2，start = 10，count = 180；2 不大于 180 退出。num = 10 + (2 - 1) / 2 = 10，offset = (2 - 1) % 2 = 1，取 "10" 的第 1 位得 0，正是 10 的个位。
代码实现
class Solution {
public int findNthDigit(int n) {
if (n < 10) {
return n;
}
long idx = n;
long digit = 1;
long start = 1;
long count = 9;
while (idx > count) {
idx -= count;
digit++;
start *= 10;
count = 9 * start * digit;
}
long num = start + (idx - 1) / digit;
int offset = (int) ((idx - 1) % digit);
return String.valueOf(num).charAt(offset) - '0';
}
}
func findNthDigit(n int) int {
if n < 10 {
return n
}
idx := int64(n)
digit := int64(1)
start := int64(1)
count := int64(9)
for idx > count {
idx -= count
digit++
start *= 10
count = 9 * start * digit
}
num := start + (idx-1)/digit
offset := int((idx - 1) % digit)
s := strconv.FormatInt(num, 10)
return int(s[offset] - '0')
}
复杂度分析
- 时间复杂度：$O(\log n)$，每轮循环让 start 乘以 10，因此循环次数等于答案所在数字的位数，n 在 int 范围内时不超过 10 轮；每轮和收尾的字符串转换都是常数级。
- 空间复杂度：$O(1)$，只用 idx、digit、start、count 等常数个 64 位变量，收尾时转出的字符串长度最多 10，可视为常数。
关键点总结
- 遇到「无限序列的第 n 项」且 n 上界极大时，先找序列的分块结构，用闭式公式整块跳过，把逐项枚举的线性复杂度压到对数。
- 每一步都要写清变量的确切含义（idx 是「区间内从 1 开始的序号」还是「从 0 开始的下标」），含义一旦漂移，减一和不减一的差别会让答案整体偏一位。
- 中间量的量级要单独估算：$9 \times 10^8 \times 9$ 已经超过 80 亿，远大于 int 上界，凡是「区间总长」这类累乘量都应该先升到 64 位。
- 把特殊元素（这里是数字 0）提前特判掉，能让主体公式保持整齐，比在通用公式里到处打补丁更可靠。
- 面试视角：这题考的是「先分块定位、再块内定位」的两级思路，讲的时候要把
(idx - 1) / digit和(idx - 1) % digit分别对应到「第几个数」和「数内第几位」；面试官常追问上界为什么用 long，以及能不能不转字符串——可以用num / 10^(digit-1-offset) % 10纯算术取位，作为加分项主动提出来。
易错点总结
- 错误写法：所有变量都用 int → 用例
n = 1000000000，计算 9 位区间的count = 9 * 100000000 * 9时溢出成负数，循环条件立刻为假，返回完全错误的数字。- 错误写法：定位时写成
num = start + idx / digit漏掉减一 → 用例n = 11，得到10 + 2/2 = 11，offset 为 0，返回 1，正确答案是 0。- 错误写法：取位时写成
offset = idx % digit→ 用例n = 1000，offset 变成 1，取到 370 的第 1 位返回 7，正确答案是 3。- 错误写法：漏掉
n < 10的特判 → 用例n = 5，进入循环时 idx = 5 不大于 9，直接算num = 1 + 4/1 = 5，虽然这个用例碰巧对，但n = 0时会算出num = 1 + (0-1)/1 = 0且 offset 为 -1，Java 抛越界异常。- 错误写法：循环条件写成
idx >= count→ 用例n = 10，idx = 10 时本该在 2 位区间的第 1 个字符处停下，但10 >= 9成立会多扣一轮，答案错位。- 错误写法：更新顺序写成先算 count 再乘 start → 用例
n = 200，count 用的还是旧的 start，得到的区间长度偏小十倍，扣减次数完全错乱。- 错误写法：忘记
start *= 10，只递增 digit → 用例n = 1000，start 恒为 1，最终num算成 271 而不是 370，返回 2。- 错误写法：把结果直接返回字符而不减
'0'→ 用例n = 1000，返回字符'3'的码点 51，判题期望的是整数 3。- 错误写法：Go 里用
string(num)而不是strconv.FormatInt(num, 10)→ 用例n = 1000，string(370)会把 370 当成 Unicode 码点转成字符ź，取字节后得到乱码值。- 错误写法：认为序列从 1 开始，把 n 先减一 → 用例
n = 10，减一后落到下标 9 上返回 9，正确答案是 10 的十位 1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 400. 第 N 位数字 | 中等 | 完全同题的英文版，注意它的下标从 1 开始，需整体平移一位 |
| 剑指 Offer 43. 1～n 整数中 1 出现的次数 | 困难 | 同样按位分段推导公式，但求的是数字 1 的累计出现次数 |
| 233. 数字 1 的个数 | 困难 | 也是按数位分块统计，但统计的是出现次数而非定位单个字符 |
| 面试题 17.06. 2出现的次数 | 困难 | 数位统计的另一变体，需要区分高位、当前位、低位的贡献 |