难度: Medium
某班级学号记录系统发生错乱，原整数学号序列 [0,1,2,3,4,...] 分隔符丢失后变为 01234... 的字符序列。请实现一个函数返回该字符序列中的第 k 位数字。
示例 1：
输入：k = 5 输出：5
示例 2：
输入：k = 12 输出：1 解释：第 12 位数字在序列 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 1 ，它是 11 的一部分。
提示：
0 <= k < 231注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/
运行时间: 32 ms
内存: 14.8 MB
class Solution:
def findNthDigit(self, n: int) -> int:
digit, start, count = 1, 1, 9
while n > count:
n -= count
start *= 10
digit += 1
count = 9 * start * digit
num = start + (n - 1) // digit
return int(str(num)[(n - 1) % digit])
首先，这个问题的关键在于理解数字序列的组织形式。数字序列以0开始，依次增长。根据数字的位数，这些数字可以分为不同的组，例如1位数(0-9)、2位数(10-99)、3位数(100-999)等。每组内的数字位数是固定的。\n\n为了找到第n位的数字，我们首先需要确定这个数字位于哪一组中。这是通过逐步减去每组中的位数来实现的，直到找到包含第n位的那个组。在代码中，变量`digit`表示当前组中每个数字的位数，`start`表示当前组的起始数字，`count`表示当前组中全部字符的总数。\n\n一旦确定了数字所在的组，我们再计算它是这个组中的第几个数字，以及是这个数字的第几位。这是通过对`start`进行偏移和使用模运算来确定的。最后，将数字转换为字符串并获取正确的字符，将其转换为整数即为答案。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def findNthDigit(self, n: int) -> int:
digit, start, count = 1, 1, 9 # 初始化位数为1，起始数字为1，当前位数组的字符总数为9
while n > count: # 当n大于当前位数组的字符总数时，需要跳至下一位数组
n -= count # 减去当前位数组的字符总数，更新n为剩余的位置数
start *= 10 # 更新起始数字到下一个位数组的起始
digit += 1 # 数字位数加1
count = 9 * start * digit # 更新当前位数组的字符总数
num = start + (n - 1) // digit # 确定n所在的完整数字
return int(str(num)[(n - 1) % digit]) # 返回n所在数字的具体某一位
在题解中，‘每组中全部字符的总数’指的是在当前位数（digit）的数字组中所有数字的字符总数。计算公式是`count = 9 * start * digit`。这里，`start`是该位数组的第一个数字（对于1位数是1，对于2位数是10，以此类推），`digit`是当前数字的位数。计算中的9是因为每组的数字范围大约是其开始的10倍减去1（例如，1位数是1到9，共9个数字；2位数是10到99，共90个数字）。因此，计算这个组中所有数字的字符总数，就是该组的数字个数乘以每个数字的字符数，即`9 * start * digit`。
循环中的终止条件`n > count`用于判断给定的位数n是否还在当前数字组的字符总数之内。如果`n`大于当前组的字符总数`count`，则意味着第`n`位数字不在当前组内，需要转至下一个数字组。通过递减`n`（即`n -= count`），我们更新`n`为排除了当前已计算组的字符后的剩余位数。这个过程不断重复，直到`n`的值不大于当前组的`count`，此时我们确定了`n`位数字确切位于当前处理的这个数字组中。
在确定了第`n`位数字位于某个具体的数字组后（假设是`digit`位数的组），`num = start + (n - 1) // digit`这行代码用于计算具体的数字。这里`start`是当前组的起始数字，`(n - 1) // digit`计算的是从组开始后，需要跳过多少个完整的数字来定位到第`n`位。例如，如果每个数字是3位数，而我们需要找到第22位，那么`(22 - 1) // 3`计算得到7，意味着从组开始的第一个数字起，跳过7个完整的数字。因此，`num`就是这个组的起始数字加上7。
使用`int(str(num)[(n - 1) % digit])`的原因是我们需要从计算出的具体数字`num`中提取特定的一位。首先，将数字`num`转换为字符串使得我们可以通过索引访问每一位。`(n - 1) % digit`计算的是在数字`num`中，第`n`位位于该数字的哪一位。例如，如果`digit`是3，我们需要找第22位，那么`(22 - 1) % 3`得到1，意味着第22位是数字中的第二位。这种方法直接、有效，而且在处理数字和字符之间的转换时非常方便。