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