[400][中等] 第N个数字

题目描述

400. 第N个数字 剑指 Offer 44. 数字序列中某一位的数字

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。

注意: n 是正数且在32位整数范围内 ( n < 231)。

示例 1:

输入:
3

输出:
3

示例 2:

输入:
11

输出:
0

说明:

• 第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。

解题思路

题目的意思相当于, 将数字以123456789101112131415...的格式序列化到一个字符序列中, 然后从中找到第n个字符.

直观感觉, 要先判断第n个字符输入哪个数字, 然后在这个数字上偏置多少位置. 一个不同位数的数字占用的字符数量不同, 我们可以先计算出来每种位数的数字占用了多少字符, 然后求他们的前缀和, 这样对于一个数字n, 就能知道它落在哪个区间之中, 对应的就得到了n对应数字的位数.

因为从数字1开始, 所以个位数共有9个数字, 十位数有90个, 百位数有900个, 因此对于位数$i,\ i=1,2,3,...$, 位数为$i$的数字共有$10^i - 10^{i - 1}$个, 对应占用的字符数就是$(10^i - 10^{i - 1}) * i$个, 将它们累加起来得到前缀和. 题目中限制了n的大小为$2^{31}$, 因此对应的位数是有限的.

计算得到的前缀区间为$[0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889, 8888888889, 98888888889]$. 索引为$i$对应的数字, 意义为考虑包含所有$i$位数在内, 以及更低位数的数字, 共占用的这样多的字符数.

对于一个数字$i$, 使用二分的方法找到这个数字所在的区间. 例如对于$n=11$, 找到的数组索引为2, 说明对应的数字为两位数. 然后就是求对应的数字是第几个二位数, 以及在这个数字中的偏移是多少. 详细的计算方法参考代码.

class Solution:
    def __init__(self):
        num_digits = len(str(2 ** 31))
        self.digit_chars = [0]
        for digit in range(1, num_digits + 1):
            num_count = 10 ** digit - 10 ** (digit - 1)
            self.digit_chars.append(self.digit_chars[-1] + num_count * digit)

    def findNthDigit(self, n: int) -> int:
        digit = bisect.bisect(self.digit_chars, n)
        digit = digit if n != self.digit_chars[digit - 1] else digit - 1
        num_resi = n - self.digit_chars[digit - 1]
        index, bias = (num_resi - 1) // digit, (num_resi - 1) % digit
        number = str(10 ** (digit - 1) + index)
        return number[bias]