0400. Nth Digit¶
题目信息¶
- 题号:
0400
- 难度:
Medium
- 主题:
无限数字序列、一基位置、十进制分段、单个数字
- 原题:
- 重点:
序列由所有正整数连续拼接、位置从 1 开始、返回所在整数中的一个十进制数字而不是整个整数
题目重述¶
把所有正整数按自然顺序写出并首尾连接,得到无限数字序列:
1234567891011121314...
给定正整数 n,返回该序列中第 n 个十进制数字。位置采用一基编号,因此第一个数字是整数 1 中的 1,第十个数字是整数 10 的第一位 1。
n 位于 [1, 2^31-1]。返回值是 0 到 9 之间的单个数字;当目标位置落在多位整数中时,需要返回该整数对应位置上的一位,而不是返回完整整数。
自建示例¶
位置落在两位数内部:
输入:n = 15
输出:2
解释:前九位是 1 到 9;第 10 至 15 位依次来自 10、11、12,第 15 位是整数 12 的个位 2。
位置仍在一位数区间:
输入:n = 9
输出:9
解释:序列前九位正好是 1、2、...、9,第九位为 9。
按位数分段定位目标整数¶
所有一位数贡献 9 * 1 位、所有两位数贡献 90 * 2 位、所有三位数贡献 900 * 3 位,依次类推。先从 n 中扣除完整位数段,直到目标落入某个固定位数的整数区间。
在当前段内,(n - 1) / digits 告诉我们目标落在哪个整数,(n - 1) % digits 告诉我们它是该整数的第几位。两个 -1 是把题目的一基位置转换成零基偏移。
C++ 实现¶
class Solution {
public:
int findNthDigit(int n) {
long long position = n;
long long digits = 1;
long long count = 9;
long long start = 1;
while (position > digits * count) {
position -= digits * count;
++digits;
count *= 10;
start *= 10;
}
long long number = start + (position - 1) / digits;
int offset = static_cast<int>((position - 1) % digits);
return std::to_string(number)[offset] - '0';
}
};
代码分析¶
每个完整位数段一次扣除,定位后只构造一个目标整数,不会拼接无限序列;使用 long long 保存段长度和位置,避免 digits * count 在 32 位范围附近溢出。位数段数量很少,时间和额外空间均为 O(log n)。