# \[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]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/shu-xue/400-dinge-shu-zi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.