题解 | #数字序列中某一位的数字#

python3，时间复杂度(logn，以10为底)。

思路和步骤：关注整体的递增的数字，而不是拆开位后的 单数字0-9。考虑上数字长度，就可以和n比较了。

1. 前期归纳总结：0位数个单数字，1位数个单数字，2位数个单数字，3位数个单数字，以此类推，这就是各个位数拥有的单数字个数。
   用n和它们比较，先确定数字的位数d（方便说明，假设是4位）
2. 确定了是4位，范围就是1000 - 9999，共个单数字。
   容易想到的是设置一个列表来记录数字，然后返回数字的某一位。比如设置[1,0,0,0]。空间复杂度O(logn)
   优化：这题关注的本不是数字，而只是单数字。所以我们只需事先确定是哪一位就行。空间复杂度O(1)
   4位的数字，确定在哪一位，只需要sd = 即可，这就确定是在d位数上的sd位上了。
3. 如果是0位，则初始是1，其他初始是0。(1000嘛)vsd = 1 if sd == 0 else 0。这就确定所在位的初始值了。
4. 如果用列表描述数字，就要粗筛细筛，分位更新。
   如果是用所在位，只需要更新这个位即可。

class Solution:
    def findNthDigit(self , n: int) -> int:
        if n == 0: return 0
        # 先找出是多少位的
        d = 1
        while d <= 9 and n > d * 9 * pow(10, d - 1):
            n = n - d * 9 * pow(10, d - 1)
            d = d + 1

        # d位数中定位在sd位上
        sd = (n - 1) % d

        # sd位的值vsd，并进行初始化
        vsd = 1 if sd == 0 else 0

        # 更新vsd
        vsd = (vsd + ((n - 1) // (d * pow(10, d - sd - 1)))) % 10

        return vsd