LeetCode 剑指 Offer 44. 数字序列中某一位的数字
题目描述
题意分析
把非负整数从小到大依次拼接成数字序列
0123456789101112…，求下标n对应的那一个十进制数字。下标从零开始，返回的是一位数字，不是包含这一位的整个整数。
n可能很大，不能真的生成前面所有字符。不同位数的正整数可以整段计数，因此先跳过完整数位段，再定位段内整数及其内部位置。
解法：分段定位
核心思路
[!blue]
n < 10时，序列前十个位置恰好对应数字零到九，直接返回n。其余情况暂时排除开头那个零，考虑从正整数一开始的拼接串：原序列的零基下标n，正好等于这个正整数拼接串中的一基位置，因此令idx = n，不额外加减。用
digit表示当前整数的位数，start表示这一段的第一个整数。该段共有9 * start个整数，每个贡献digit个字符，所以整段长度为count = 9 * start * digit。若
idx > count，目标不在这一段，扣掉整段字符数，再令位数加一、起始整数乘十。恰好等于count时，目标仍是当前段的最后一位，不能进入下一段。确定所属段后，将一基位置减一得到零基偏移。
(idx - 1) / digit表示已经越过多少个完整整数，目标整数就是start + (idx - 1) / digit；(idx - 1) % digit表示它内部从左到右的字符下标。只把这个目标整数转换成十进制字符串，再读取对应字符即可。整段字符数量可能比输入下标大很多，
idx、start、count及目标整数都使用宽整数，不能因为最后只返回一位数字就用窄类型保存中间值。
解题步骤
n < 10时直接返回n。- 初始化剩余位置
idx = n，当前位数为一、起始整数为一，整段字符数为九。- 当
idx严格超过当前段长度时扣除整段，并更新下一位数段的信息。- 用
(idx - 1) / digit定位目标整数，用(idx - 1) % digit定位其内部字符。- 读取这个字符并减去
'0'，返回对应数字。
代码实现
class Solution {
public int findNthDigit(int n) {
if (n < 10) {
return n;
}
// 排除序列开头的零后，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';
}
}
import "strconv"
func findNthDigit(n int) int {
if n < 10 {
return n
}
// 排除序列开头的零后，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+1))$，按位数跳段，再转换一个相应位数的整数；小下标直接常数时间返回。
- 辅助空间复杂度：$O(\log(n+1))$，用于目标整数的十进制字符串。在题目固定整数范围内，它有固定长度上界。
关键点总结
[!green]
- 去掉序列开头的零后，原下标直接对应正整数拼接串的一基位置。
- 先按位数段整体跳过，再用整除和取余拆出两级位置。
- 段内定位前先减一，段长度计算使用宽整数。
易错点总结
[!yellow]
- 扣除整段的条件是
idx > count，用大于等于会错过本段最后一个字符。- 一基位置未减一就整除、取余，会在整数边界产生偏移。
- 输入序列包含最开始的零，不能直接照搬从正整数一开始且输入也是零基下标的版本。
9 * start * digit可能超出 32 位，必须让乘法从宽整数开始计算。- 返回的是目标整数中的某位字符对应的数字，不是目标整数本身。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 233. 数字 1 的个数 | 困难 | 同样按十进制位数分块统计，本题跳过整段数字占据的位数，原题累计某个数码的出现次数。 |
| 440. 字典序的第K小数字 | 困难 | 同样跳过大块候选而不逐个生成，原题按字典序前缀分块，本题按普通数值顺序的位数分块。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！