LeetCode 400. 第 N 位数字
题目描述
题意分析
把正整数
1、2、3、…的十进制表示依次拼接，得到连续的数字字符序列，返回其中从1开始计数的第n位数字。答案是0到9中的一个数，不是第n个整数，也不是包含目标位的整个整数。
n最大可到 32 位有符号整数上限，逐个生成并拼接到目标位置会产生不必要的大量时间和空间开销。可以利用相同位数的整数具有相同长度，成组跳过前面的数字。
解法：按位数分组定位
核心思路
[!blue]
把正整数按十进制位数分组。当前组的每个整数有
digit位，第一个整数为start = 10^(digit - 1)，共有count = 9 * start个整数，因此整组贡献digit * count个字符。用
remain表示跳过前面完整分组后，目标在剩余序列中从一开始的排名。若remain > digit * count，目标不在本组，减去整组字符数，再进入下一位数组。若小于或等于，目标就在当前组；等于时恰好是本组最后一位，不能再跳过。定位到分组后，将一基排名转为零基偏移
remain - 1。除以digit的商表示完整跨过了多少个本组整数，所以包含目标位的整数为num = start + (remain - 1) / digit；余数index = (remain - 1) % digit表示目标在这个整数中从左数的零基位置。目标位右边还有
digit - index - 1位。把num连续除以十这么多次，目标位就移到了个位，再取num % 10即可。这个过程不必把整数转换成字符串。即使输入
n能放入 32 位整数，完整分组的字符总数也可能超过这个范围。代码从一开始使用 Java 的long、Go 的int64保存分组变量，让乘法在宽整数类型中完成。
解题步骤
- 初始化
digit = 1、start = 1、count = 9、remain = n。- 当
remain > digit * count时，减去当前组字符数，将digit加一，并让start、count各乘十。- 计算
num = start + (remain - 1) / digit和index = (remain - 1) % digit。- 将
num除以十共digit - index - 1次，去掉目标位右侧的数字。- 返回
num % 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)$，只维护若干宽整数变量，不构造拼接序列或辅助字符串。
关键点总结
[!green]
count是整数个数，digit * count才是分组贡献的字符数量，跳过时不能混淆单位。- 先把剩余排名减一，商负责定位整数，余数负责定位整数内部的字符。
- 余数从左端计数，而取模只能读取个位，需要先去掉目标位右侧的低位。
- 分组乘法本身必须在宽整数类型中执行，不能溢出后再转换结果。
易错点总结
[!yellow]
- 跳组条件写成
>=，会把恰好落在本组最后一位的目标错误移到下一组，应使用严格大于。- 忘记将
remain减一就求商和余数，会在每个整数的末尾产生错位。- 把拼接序列当作从整数零开始，会多算一位；本题从正整数一开始。
- 定位整数后直接返回
num % 10，只能得到该整数的最后一位，必须先移除目标右侧的数字。- 使用 32 位变量保存完整分组的字符总数，可能在比较目标是否越过本组之前就发生溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 233. 数字 1 的个数 | 困难 | 同样按十进制位数分块统计，本题跳过整段数字占据的位数，原题累计某个数码的出现次数。 |
| 440. 字典序的第K小数字 | 困难 | 同样跳过大块候选而不逐个生成，原题按字典序前缀分块，本题按普通数值顺序的位数分块。 |