跳至主要內容

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

ITCharge大约 1 分钟

剑指 Offer 44. 数字序列中某一位的数字open in new window

  • 标签:数学、二分查找
  • 难度:中等

题目链接

题目大意

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

要求:返回任意第 n 位对应的数字。

解题思路

根据题意中的字符串,找数学规律:

  • 123456789:是 91 位数字。

  • 10111213...9899:是 902 位数字。

  • 100...999:是 9003 位数字。

  • 1000...999990004 位数字。

  • 我们可以先找到对应的数字对应的位数 digits

  • 然后找到该位数 digits 的起始数字 start

  • 再计算出 n 所在的数字 numbernumber 等于从起始数字 start 开始的第 (n1)/digits\lfloor(n - 1) / digits\rfloor 个数字。即 number = start + (n - 1) // digits

  • 然后确定 n 对应的是数字 number 中的哪一位。即 idx = (n - 1) % digits

  • 最后返回结果。

代码

class Solution:
    def findNthDigit(self, n: int) -> int:
        digits = 1
        start = 1
        base = 9
        while n > base:
            n -= base
            digits += 1
            start *= 10
            base = start * digits * 9

        number = start + (n - 1) // digits
        idx = (n - 1) % digits
        return int(str(number)[idx])

参考资料