LeetCode 400. 第 N 位数字
目录
题目描述
题意分析
把正整数按 1、2、3、…… 的顺序首尾相接写成一条无限长的字符流「123456789101112……」，题目要求返回这条字符流上第
n个字符所代表的数字。注意被返回的是「一个字符」而不是「一个整数」：第 11 位落在数字 10 的内部，答案是 0 而不是 10。所以定位工作有两层，先要找到第
n位属于哪个整数，再要找到它是那个整数从左数第几位。约束里
n最大到 $2^{31}-1$，也就是约二十一亿。这个量级明确排斥了「一个一个数字往下拼」的做法，同时也是一个强烈的提示：中间量随时可能顶到甚至越过 32 位整数的上界。边界上要留意两点：
n从 1 开始计数而不是从 0 开始；序列从 1 开始而不含 0，所以一位数只有 9 个而不是 10 个。
解法：按位数分组定位
核心思路
不能真的生成长度为
n的字符串。按整数位数分组：digit位正整数有 $9 \times 10^{digit-1}$ 个，这一组共贡献digit * count个字符。逐组扣减，便能一次跳过整段。循环不变量：
digit、start、count分别表示当前组的位数、首个整数和整数个数；remain是目标字符在当前组中的 1 基序号。每跳过一组就扣掉该组字符数，并更新三项信息，不变量保持成立。找到目标组后，把
remain - 1转成 0 基偏移：
- 目标整数：
num = start + (remain - 1) / digit；- 目标位下标：
index = (remain - 1) % digit，从左侧 0 开始。组与组互不重叠且覆盖整个序列；组内再由商、余数唯一确定整数和数位，因此定位不会遗漏或重复。最后去掉目标位右侧的
digit - index - 1位，再对 10 取模即可。
解题步骤
- 初始化
digit = 1、start = 1、count = 9、remain = n。- 当
remain > digit * count时，扣掉当前组的字符数，并进入下一位数分组。- 用
(remain - 1) / digit定位目标整数，用(remain - 1) % digit定位整数内部的数位。- 将目标位右边的低位逐位除掉，返回
num % 10。例如
n = 11：先跳过 9 个一位数字符，得到两位数组内偏移remain = 2；目标整数是10，内部下标是 1，即个位 0。边界n = 9仍在一位数组，n = 10则是数字 10 的最高位。
代码实现
class Solution {
public int findNthDigit(int n) {
long digit = 1;
long start = 1;
long count = 9;
long remain = n;
while (remain > digit * count) {
remain -= digit * count;
digit++;
start *= 10;
count *= 10;
}
long num = start + (remain - 1) / digit;
long index = (remain - 1) % digit;
for (long remove = digit - index - 1; remove > 0; remove--) {
num /= 10;
}
return (int) (num % 10);
}
}
func findNthDigit(n int) int {
digit := int64(1)
start := int64(1)
count := int64(9)
remain := int64(n)
for remain > digit*count {
remain -= digit * count
digit++
start *= 10
count *= 10
}
num := start + (remain-1)/digit
index := (remain - 1) % digit
for remove := digit - index - 1; remove > 0; remove-- {
num /= 10
}
return int(num % 10)
}
复杂度分析
- 时间复杂度：$O(\log n)$。位数组数量及最后的取位次数都与十进制位数同阶。
- 空间复杂度：$O(1)$。只使用若干 64 位整数变量。
关键点总结
- 先按位数分组，再做组内定位，避免逐个生成数字。
- 商确定目标整数，余数确定整数内的数位；二者都要使用
remain - 1。digit * count在 9 位数组已达到 81 亿，Java 中间量必须使用long。- 面试时用
n = 9、10、11检查组边界和 1 基转 0 基是否正确。
易错点总结
- 分组乘法使用
int：9 位数组的字符数是9 * 900000000，会溢出 32 位整数。- 忘记
remain - 1：n = 9会被定位到数字 10，而不是数字 9。- 跳组条件写成
>=：目标恰好位于当前组末尾时会被错误地跳到下一组，应使用>。- 把序列当成从 0 开始：本题一位数只有 1 到 9，共 9 个。
- 直接返回
num % 10：n = 10的目标是数字 10 的最高位 1，必须先去掉目标位右侧的数字。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 剑指 Offer 44. 数字序列中某一位的数字 | 中等 | 同一模型的另一版本，序列从 0 开始，首段长度与偏移都要重算 |
| 233. 数字 1 的个数 | 困难 | 从「定位某一位」转为「统计某个数字出现次数」，按位拆成高位与低位贡献 |
| 面试题 17.06. 2出现的次数 | 困难 | 同为按位统计，但目标数字非 1，最高位的边界讨论不同 |
| 9. 回文数 | 简单 | 同样用整除与取模逐位拆解整数，但要求不借助字符串反转比较 |
| 7. 整数反转 | 中等 | 逐位重组整数，重点在反转过程中的溢出判定而非定位 |