题目

题目描述

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

请写一个函数，求任意第n位对应的数字。

示例1

输入: n = 3
输出: 3

示例2

输入: n = 11
输出: 0

题解

(引用Krahets)

位数规律

计算当前所在的位数范围，其次确定对应数字，最后找出对应该数字的第几位。

1. 确定所求数位的所在数字的位数 digit;
2. 确定所求数位所在的数字 num;
3. 确定所求数位在 num 的哪一数位;

时间复杂度: O(logn)，循环最多logn次，num转为字符串占用O(n);
空间复杂度: O(logn)，num转为字符串占O(logn)额外空间;

class Solution:
    def findNthDigit(self, n: int) -> int:
        digit, start, count = 1, 1, 9
        while n > count:
            n -= count
            digit += 1
            start *= 10
            count = 9 * start * digit
        num = start + (n - 1) // digit
        return int(str(num)[(n - 1) % digit])