考查应聘者面对复杂问题的思维能力。应聘者需要有严密的数学思维能力，并且还要通过分析具体例子一步步找到通用的规律，才能想出好的算法。这些能力在实际工作中面对复杂问题的时候都非常有用。

Question

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

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

限制：\(0 <= n < 2^{31}\)

测试用例

功能测试（输入10、190、1000等）。 边界值测试（输入0、1等）。

本题考点

考查应聘者做优化的激情和能力。最直观的方法很多应聘者都能想到。当面试官提示还有更快的方法之后，应聘者千万不要轻易放弃尝试。虽然想出好的方法不容易，但应聘者要展示自己追求更快算法的激情，多尝试不同的方法，必要的时候可以要求面试官给出提示，但不能轻易说自己想不出来并且放弃努力。 考查应聘者面对复杂问题的思维能力。应聘者需要有严密的数学思维能力，并且还要通过分析具体例子一步步找到通用的规律，才能想出好的算法。这些能力在实际工作中面对复杂问题的时候都非常有用。

Intuition

简单思路

从0开始逐个遍历，每遍历过一个数字，就将 count 变量加1，直到 count 等于 n 为止。

优化思路

可以找出某些规律从而跳过若干数字，接下来用一个具体的例子来分析如何解决这个问题。比如，序列的第1001位是什么？ 序列的前10位是0_{9这10个只有一位的数字。显然第1001位在这10个数字之后，因此这10个数字可以直接跳过。我们再从后面紧跟着的序列中找第991（991=1001-10）位的数字。 接下来180位数字是90个10}99的两位数。由于991>180，所以第991位在所有的两位数之后。我们再跳过90个两位数，继续从后面找881（881=991-180）位。 接下来的2700位是900个100~999的三位数。由于811<2700，所以第811位是某个三位数中的一位。由于811=270×3+1，这意味着第811位是从100开始的第270个数字即370的中间一位，也就是7。

Code

• 简单思想，超出时间限制。

class Solution:
    def findNthDigit(self, n: int) -> int:
        _str = ''.join([str(i) for i in list(range(n+1))])
        return int(_str[n])

• 仔细分析优化之后的代码

class Solution:
    def countOfIntergers(self, digit):
        """计算digit位的数字共有多少个 10（0-9），90（10-99），900（100-999）
        """
        if digit == 1:
            return 10
        count = 10 ** (digit-1)
        return 9 * count
    
    def digitAtIndex(self, index, digits):
        """确定具体位置上的数是多少
        """
        number = int(self.beginNumber(digits) + index/digits)  # 计算出index那一位数字，具体在哪个数字中，例如index=1001的数字在370这个数字中。
        position = digits - index % digits  # 计算出index那一位数字，具体在哪一位，例如，输入index=1001，对应在370（number）这个数字的第2（position）位。
        for i in range(1, position):  # 从第1位开始循环
            number //= 10
        return number % 10
    
    def beginNumber(self, digit):
        """计算digit位的数字第一位的值 0，10，100
        """
        if digit == 1:
            return 0
        return 10 ** (digit-1)

    def findNthDigit(self, n: int) -> int:
        """求解数字序列中的一个数
        """
        index = n
        if index < 0:
            return -1
        digits = 1
        while True:
            numbers = self.countOfIntergers(digits)
            if index < numbers * digits:  # 假设digits=2，number=90，那么之后的180个数，都是属于2进制的数。
                return self.digitAtIndex(index, digits)
            index -= numbers * digits  # 如果范围在这180个数字之后，直接跳过即可。
            digits += 1
        return -1