Jianbo Dai's

jz044.数字序列中某一位的数字

 
  • Jul 17, 2020

题目链接

对于该题的直观想法大概是从0开始逐一枚举每一个数字，每枚举一个数字就求出某个数字有几位并将该数字的位数与前面的所有数字位数和累加。如果位数之和小于或等于输入n，则继续枚举，若大于，则所求必定在最新的数字里。但是显然这个思路会很慢，我们又可以试着去找找数字的规律。我们用例子，序列的第1001位是什么来阐述另外一种方法。

首先，对于序列的前10位，是0-9这十个只有一位的数字，我们显然可以跳过，那我们就可以在后面紧跟着的序列中找第991位的数字（991 = 1001 - 10）。又易知，接下来的180位数字是90个10-99的两位数，由于991 > 180，我们又可以跳过这一段，考虑接下去序列的第881位（881 = 991 - 180）。接下去我们会有900个100-999的三位数，所占的总长为2700，由于811 < 2700，所以第881位是某个三位数中的一位，由于811 = 270 * 3 + 1，这意味着第881位是从100开始的第270个数字（即370）的中间一位，也即是7。我们用代码表述这种思路。这个算法的时间复杂度因为循环的最大次数为O（logN）次，因此是O（logN），空间复杂度是O（logN），是因为str（num）占用了额外O（logN）的空间。代码2是别人实现得更整洁一点的代码。

class Solution:
    def findNthDigit1(self, n: int) -> int:
        if n == 0:
            return 0
        curLen = 1
        digit = 1
        lenInv = 1
        while curLen <= n:
            tmpLen = n - curLen
            curLen += lenInv * (digit * 10 - digit)
            digit *= 10
            lenInv += 1
        res = str(digit // 10 + tmpLen // (lenInv - 1))[tmpLen % (lenInv - 1)]
        return int(res)

    def findNthDigit2(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])
Search