> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/shu-xue/400-dinge-shu-zi.md).

# \[400]\[中等] 第N个数字

## 题目描述

[400. 第N个数字](https://leetcode-cn.com/problems/nth-digit/) [剑指 Offer 44. 数字序列中某一位的数字](https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/)

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

注意: n 是正数且在32位整数范围内 ( n < 231)。

示例 1:

```
输入:
3

输出:
3
```

示例 2:

```
输入:
11

输出:
0
```

说明:

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

## 解题思路

题目的意思相当于, 将数字以123456789101112131415...的格式序列化到一个字符序列中, 然后从中找到第`n`个字符.

直观感觉, 要先判断第`n`个字符输入哪个数字, 然后在这个数字上偏置多少位置. 一个不同位数的数字占用的字符数量不同, 我们可以先计算出来**每种位数的数字占用了多少字符**, 然后求他们的前缀和, 这样对于一个数字`n`, 就能知道它落在哪个区间之中, 对应的就得到了`n`对应数字的位数.

因为从数字`1`开始, 所以个位数共有9个数字, 十位数有90个, 百位数有900个, 因此对于位数$$i,\ i=1,2,3,...$$, 位数为$$i$$的数字共有$$10^i - 10^{i - 1}$$个, 对应占用的字符数就是$$(10^i - 10^{i - 1}) \* i$$个, 将它们累加起来得到前缀和. 题目中限制了`n`的大小为$$2^{31}$$, 因此对应的位数是有限的.

计算得到的前缀区间为$$\[0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889, 8888888889, 98888888889]$$. 索引为$$i$$对应的数字, 意义为考虑包含所有$$i$$位数在内, 以及更低位数的数字, 共占用的这样多的字符数.

对于一个数字$$i$$, 使用**二分**的方法找到这个数字所在的区间. 例如对于$$n=11$$, 找到的数组索引为`2`, 说明对应的数字为两位数. 然后就是求对应的数字是第几个二位数, 以及在这个数字中的偏移是多少. 详细的计算方法参考代码.

```python
class Solution:
    def __init__(self):
        num_digits = len(str(2 ** 31))
        self.digit_chars = [0]
        for digit in range(1, num_digits + 1):
            num_count = 10 ** digit - 10 ** (digit - 1)
            self.digit_chars.append(self.digit_chars[-1] + num_count * digit)

    def findNthDigit(self, n: int) -> int:
        digit = bisect.bisect(self.digit_chars, n)
        digit = digit if n != self.digit_chars[digit - 1] else digit - 1
        num_resi = n - self.digit_chars[digit - 1]
        index, bias = (num_resi - 1) // digit, (num_resi - 1) % digit
        number = str(10 ** (digit - 1) + index)
        return number[bias]
```