英文原文
Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].
Example 1:
Input: n = 3 Output: 3
Example 2:
Input: n = 11 Output: 0 Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
Constraints:
1 <= n <= 231 - 1
中文题目
给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
示例 1：
输入：n = 3 输出：3
示例 2：
输入：n = 11 输出：0 解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
提示：
1 <= n <= 231 - 1- 第
n位上的数字是按计数单位（digit）从前往后数的第n个数，参见 示例 2 。
通过代码
高赞题解
模拟
我们知道，对于长度为 $len$ 的数字的范围为 $[10^{len - 1}, 10^{len} - 1]$（共 $9 * 10^{len - 1}$ 个），总长度为：
$$
L = len * 9 * 10^{len - 1}
$$
因此我们可以先对 $n$ 进行不断试减（更新 $n$），确定下来目标数字 $x$ 的长度为多少，假设为 $len$。
然后直接计算出长度 $len$ 的最小值为 $s = 10^{len - 1}$，由于范围内的数长度都是 $len$，因此我们可以直接定位到目标数字 $x$ 为何值。
根据目标值 $x$ 必然满足关系式：
$$
(x - s + 1) * len \geq n
$$
变形可得：
$$
x \geq \left \lfloor \frac{n}{len} \right \rfloor - 1 + s
$$
对 $n$ 进行最后一次的试减（更新 $n$），若恰好有 $n = 0$，说明答案为 $x$ 的最后一位，可由 x % 10 取得；若大于 $0$，说明答案是 $x + 1$ 的第 $n$ 位（十进制表示，从左往右数），可由 (x + 1) / (int) (Math.pow(10, len - n)) % 10 取得。
代码：
[]class Solution { public int findNthDigit(int n) { int len = 1; while (len * 9 * Math.pow(10, len - 1) < n) { n -= len * 9 * Math.pow(10, len - 1); len++; } long s = (long) Math.pow(10, len - 1); long x = n / len - 1 + s; n -= (x - s + 1) * len; return n == 0 ? (int) (x % 10) : (int) ((x + 1) / Math.pow(10, len - n) % 10); } }
- 时间复杂度：$O(\log{n})$
- 空间复杂度：$O(1)$
补充
看到评论区，不少小伙伴对上述推导理解感到困难。我们可以换个思路，从更加纯粹直接的角度进行分析。
首先和上述解法一样，我们还是需要先对 $n$ 进行第一阶段的试减（更新 $n$），得到目标数字所在的数值的长度 $len$ 是多少。
然后根据 $len$ 我们可以算得起点值 $s = 10^{len - 1}$（例如 $len = 2$ 时，$s = 10$；$len = 3$ 时，$s = 100$）。
由于每个数长度都是 $len$，因此我们可以用剩余的数 $n$ 除 $len$，得到从起点的偏移量是多少（并将偏移量累加更新到 $s$），然后对 $n$ 做第二阶段的试减，减去的值就是 $\left \lfloor \frac{n}{len} \right \rfloor * len$。
如果试减后结果恰好为 $0$，那么答案为当前 $s$ 的最后一个数字；否则（试减结果大于 $0$），则是 $x + 1$ 中（十进制表示，从左往右数）的第 $n$ 个数字。
代码：
[]class Solution { public int findNthDigit(int n) { int len = 1; while (len * 9 * Math.pow(10, len - 1) < n) { n -= len * 9 * Math.pow(10, len - 1); len++; } long s = (long) Math.pow(10, len - 1); s += n / len - 1; n -= len * (n / len); return n == 0 ? (int) (s % 10) : (int) ((s + 1) / Math.pow(10, len - n) % 10); } }
- 时间复杂度：$O(\log{n})$
- 空间复杂度：$O(1)$
最终你会发现，两种做法是完全等价的，只是对应了不同的角度描述而已。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 41650 | 91694 | 45.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
