博客

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


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

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

示例 1：

输入：n = 3

输出：3

示例 2：

输入：n = 11

输出：0

限制：

0 <= n < 2^31

• 首先是确定数位，例如数位一在索引[0,9].数位二在索引[10,189],数位三在索引[190, 2889]
• 确定数位之后就可以减去前面的数位所含有的索引值，从当前数位开始寻找。
• 比如减去之前的数值之后当前的数值是 10，当前的数位为2.我们可以知道这是数位2后的第5个数
• 计算的方法就是差值对数位相除取模， 商就是所在的位数，余数就是这个数的第几位。
• 例如 11 / 2 = 5 ···1，那么10+5+1 = 16,余数为1，即 1-1 = 0，16的第0位数。
• 解释下如果商为0，那么就是10，就是第一个二位数，商为1，就是第2个二位数11。
• 余数和索引的关系就是余数减一等于索引值。
• 还有一种刚好除尽的情况，即 b == 0, 根据上述关系我们直到知道这是前一个数的最后一位。

class Solution:
    def findNthDigit(self, n: int) -> int:
        if not n: return 0
        layer = 0
        num = 0
        pre = 0
        while n > num:#确定当前数的数位
            layer += 1
            pre = num
            num = num + (10**layer - 10**(layer-1))*layer
        #算出当前索引值的位数[一位数，两位数。。。]
        # print(pre, num, layer)
        n -= pre#确定数位之后就可以减去前面的一段数值，在这个数位里面寻找
        a, b = divmod(n, layer)
        # print(a, b, n , layer)

        if b == 0:#前一个数的最后一位
            out = 10**(layer-1) + a - 1
            return int(str(out)[-1])
        else:
            out = 10**(layer-1)
            return int(str(out)[b-1])