剑指offer-44

剑指 Offer 44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例

输入：n = 3
输出：3

输入：n = 11
输出：0

官方题解

解体思路：

1. 将$101112 \cdots$ 中的每一位称为 数位，记为 $n$；

2. 将$10, 11, 12, \cdots$ 称为数字，记为 $num$；

3. 数字 $10$ 是一个两位数，称此数字的 位数为2，记为 $digit$；

4. 每 $digit$ 位数的起始数字（既：$1,10,100,\cdots$），记为 $start$；

   

观察上表，可推出各 $digit$下的数位数量 $count$的计算公式：
$$
count = 9 * start * digit
$$
根据以上分析，可将求解分为三步：

1. 确定$n$所在数字的位数，记为$digit$
2. 确定$n$所在的数字，记为$num$
3. 确定 $n$ 是 $num$中的哪一位数位，并返回结果

1. 确定所求数位的所在数字的位数

如下图所示，循环执行 $n$ 减去一位数、两位数、$\dots$的数位数量 $count$，直到 $n \leq count$时跳出。

由于 $n$ 已经减去了一位数、两位数、$\dots$ 、（$digit-1$）位数的 数位数量 $count$，因而此时的 $n$ 是从起始数字 $start$ 开始计数的。

digit, start, count = 1,1,9

# n相当于总数位，各个位数的数位数量相加得到
while n > count:
    n -= count
    start *= 10 # 1, 10, 100, .. 起始位数
    digit += # 1,2,3， # 数的位数
    count = 9 * start * digit # 9, 180, 2700，数位的数量

结论： 所求数位 ① 在某个 $digit$位数中； ② 为从数字 $start$ 开始的第 n 个数位。

2. 确定所求数位所在的数字

如下图所示，所求数位 在从数字 $start$ 开始的第 $[\frac{n-1}{digit}]$个 数字中（$start$为第0个数字）。

num = start + (n-1) // digit

结论： 所求数位在数字 $num$ 中。

3. 确定所求数位在 $num$ 的哪一数位

如下图所示，所求数位为数字 $num$ 的第 $(n-1)% digit$位（数字的首个数位为第0位）。

s = str(num) # 转化为 string
res = int(s[(n - 1) % digit]) # 获得 num 的 第 (n - 1) % digit 个数位，并转化为 int

结论： 所求数位是 $res$ 。

class Solution:
    def findNthDigit(self, n: int) -> int:

        digit = 1
        start = 1
        count = 9

        while n > count:
            n -= count
            start *= 10
            digit += 1 # 数字的位数加一
            count = 9*start*digit # 统计当前位数的数字数量
        
        num = start + (n-1) // digit

        res = str(num)[(n-1)%digit]
        return int(res)