难度: Medium
给你一个整数 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
Submission
运行时间: 20 ms
内存: 16.5 MB
class Solution:
def findNthDigit(self, n: int) -> int:
digit, start, count = 1, 1, 9
while n > count: # 1.
n -= count
start *= 10
digit += 1
count = 9 * start * digit
num = start + (n - 1) // digit # 2.
return int(str(num)[(n - 1) % digit]) # 3.
Explain
这个题解的思路是先确定第 n 位数字所在的数字的位数，然后确定该数字，最后确定该数字的第 n 位。具体来说： 1. 首先通过 while 循环确定第 n 位所在的数字的位数 digit，同时更新剩余的 n。 2. 然后根据剩余的 n 和位数 digit 计算出第 n 位所在的数字 num。 3. 最后将 num 转为字符串，并取出第 (n-1) % digit 个字符，转换为整数作为结果返回。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def findNthDigit(self, n: int) -> int:
digit, start, count = 1, 1, 9
while n > count: # 确定 n 所在的数字的位数
n -= count
start *= 10
digit += 1
count = 9 * start * digit
num = start + (n - 1) // digit # 确定 n 所在的数字
return int(str(num)[(n - 1) % digit]) # 返回数字的第 n 位
Explore
在题解中，变量 'count' 的计算公式 'count = 9 * start * digit' 是用来确定在当前位数 'digit' 下所有数字的总位数。这里的 'start' 表示该位数下的第一个数字（如：1, 10, 100 等），而 'digit' 表示当前数字的位数（如：1位数、2位数）。因此，从 'start' 开始的前 9 个数（如：1 到 9, 10 到 99, 100 到 999 等）包含的总位数就是 '9 * start * digit'。这个公式帮助算法快速跳过大量数字，直到找到包含第 n 位的具体数字。
在计算变量 'num' 时使用的公式 'start + (n - 1) // digit' 是为了找出具体包含第 n 位的整数。这里的 'start' 是当前位数的第一个数字，而 '(n - 1) // digit' 是计算从 'start' 开始后应该跳过多少个整数才能到达包含第 n 位的数字。这个公式的含义是在已知每个数字占用 'digit' 个位置的情况下，计算并跳过前面的完整数字，直接定位到包含目标位的数字。
题解中使用 '(n - 1) % digit' 是为了定位在数字 'num' 中第 n 位所在的具体位置。由于 'num' 是由多个数字位组成，'digit' 是每个数字的位数。因此，'(n - 1) % digit' 计算的是在数字 'num' 中，第 n 位是从左到右的第几位（从0开始计数）。这样就能精确地提取出 'num' 的特定一位，转换成整数后作为结果返回。
在题解的 while 循环中，每次循环都会检查 'n > count' 来决定是否继续减去 'count'。这个循环保证了只有当 'n' 大于当前 'count' 时，才会进行减法操作。一旦 'n' 不大于 'count'，循环就会停止。因此，'n' 不会减到0或变负。在循环结束时，'n' 会是一个有效的、正好指向所需数字位的正整数，确保算法可以正确地继续计算 'num' 以及从 'num' 中取得具体的一位数字。