Leetcode 400. 第N个数字

题目描述

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。

示例 1:

输入: 3

输出: 3

示例 2:

输入: 11

输出: 0

说明: 第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。

题目中所谓的第 n 个数字，指的是数字构成的字符串中的第 n 位上数字。

解法

观察数字规律可知：

一位数共有：

两位数共有：

三位数共有：

位数共有：

由此可获得第 n 位数字属于哪个分段，即可知 m 的值。由 (n-1)//m 可获得第 n 位数字所属于数值，在该分段所有数值列表的下标。例如 3 在一位数分段的下标为 2；11 在两位数分段的下标为 0。分段的起始数值为

，则第 n 位数字所属数值为

。第 n 位数字在数值 num 中的下标为

，由此可知第 n 位数字。

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