问题
Leetcode 400 — 第 N 位数字
分析
首先，很容易观察到：
- 数字 0-9 只有 1 位，
- 数字 10-99 有 2 位，
- 数字 100-999 有 3 位，依此类推。
换句话说：
1 位数字中有 9*1(9e0*1) 位，2 位数字中有 90*2(9e1*2) 位，3 位数字中有 900*3(9e2*3) 位……
然后我们可以很容易地得到一个数组，包含每组 i 位数字的所有位数
bounds = [9e0, 9e1*2, 9e2*3, 9e3*4, 9e4*5, 9e5*6, 9e6*7, 9e7*8, 9e8*9, 9e9*10, 9e10*11]
这使我们能够快速确定需要多少位数才能到达包含目标数字的组。
示例 1：
n = 10，因此显然 10 可以覆盖 9*1，剩下 1 位，这不足以覆盖 90*2。所以当 n = 10 时，结果必须在一个 2 位数字中，并且是所有 2 位数字的第 1 位，也就是数字 10 中的 1。
示例 2：
n = 1000，很明显，1000可以覆盖9*1和90*2，剩余的数字为1000 – 9 – 180 = 811位，这不足以覆盖900*3，因此显然结果必须是一个3位数，并且是所有3位数中的第811位数字。
解决方案
根据上述分析，接下来的步骤很明确。
一旦我们知道：
- 数字的位数（digit_range）
- 剩余数字的数量（remaining_digits）
我们就可以找到包含结果的数字：
number = 10 ** (digit_range-1) + remaining_digits // digit_range
if remaining_digits % digit_range == 0:
number = number - 1注意：
如果 remaining_digits 正好能被 digit_range 整除，数字应该 减一
例如：digit_range = 2，remaining_digits = 2，结果应该是数字 10 的第 2 位，即 0
但如果不减，则会是 10*1 + 2//2 = 11，这是错误的。
现在我们得到了数字，最后一步是获取结果在数字中的 digit_index，这非常简单：
digit_index = remaining_digits % digit_range
为了方便获取每个索引的数字，我们将数字转换为字符串。
由于 Python（以及大多数编程语言）使用 0 基索引,
我们可以安全地将数字转换为字符串并提取数字：
numberStr = str(int(number))
return int(numberStr[int(digit_index) - 1])
由于在Python中，索引-1指向可迭代对象的末尾，因此对于那些完全被digit_range整除的剩余部分，结果自动指向最后一位数字，这完全是正确的答案。
完整代码
class Solution:
def findNthDigit(self, n: int) -> int:
bounds = [9e0, 9e1*2, 9e2*3, 9e3*4, 9e4*5, 9e5*6, 9e6*7, 9e7*8, 9e8*9, 9e9*10, 9e10*11]
digits = [1,2,3,4,5,6,7,8,9,10]
digit_range = 0 # 数字中的位数
for i in range(0,11,1):
if n > bounds[i]:
n -= bounds[i]
else:
digit_range = digits[i]
break
remaining_digits = n
number = 10 ** (digit_range-1) + remaining_digits // digit_range
if remaining_digits % digit_range == 0:
number = number - 1
digit_index = remaining_digits % digit_range # 数字中位数的索引
numberStr = str(int(number))
return int(numberStr[int(digit_index)-1])
