面试题44：数字序列中的某一位数

题目：
数字以012345678910111213141516.....的格式序列化到一个字符串序列中。在这个序列中。第五位(从0开始计数)是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

思路：
这道题目最直观的是逐个枚举法，但是这样的效率不够高。于是我们想办法使得能够跳过一些数，提高效率。总结规律如下：序列前10位是只有一位数的数字；接下来的180位是90个10-99的数字，接着是2700位三位数的数字。因此解决本题的思路如下：(还有一个关于最终的位置的小疑问)、

44 数字序列中的某一位数字.png

代码实现：

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            return -1
        digit = 1
        while True:
            number = self.HasNum(digit)
            if n < digit*number:    #索引小于该该位数*对应的数字个数，说明就在这个区间内
                return self.digitIndex(n, digit)   #寻找具体的数字
            else:
                n -= digit* number   #减去这些数字继续向后寻找
                digit +=1
        return -1

        

    def HasNum(self, digit):
        if digit == 1:
            return 10
        else:
            count = 10**(digit-1)
            return 9*count
    
    def digitIndex(self, n, digit):
        #1.找到n位数开始的数字
        if digit == 1:
            begin = 0
        else:
            begin = 10**(digit-1)
        #2.找到具体的数字
        finalNum = begin + n//digit
        #3.找到在数字中的位置，取出数字
        position = digit- n % digit   # 这里是为了取整最终得到个位的元素
        if position > 0:
            for i in range(1,position):
                finalNum = finalNum//10
        return finalNum % 10

提交结果：

leetcode提交结果