数字序列中某一位的数字

## 1 题目

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

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

**示例 1：**

```txt
输入：n = 3
输出：3
```

**示例 2：**

```txt
输入：n = 11
输出：0
```

**限制：**

* 0 <= n < 2^31

## 2 问题分析

1. 相应的数字定义如下：

1. **将 $ 101112 \cdots$ 中的每一位称为数位**，**记为 $n$**。
   2. **将 $ 10, 11, 12, \cdots$ 称为数字**，**记为 $num$**。
   3. **数字 $ 10 $ 是一个两位数**，**称此数字的位数为 2**，**记为 $digit$**。
   4. **每 $digit$ 位数的起始数字**（即 $ 1, 10, 100, \cdots$），**记为 $start$**。

![Picture1.png](/media/202202/2022-02-09_1733270.5518137850928253.png)
2. 根据以上分析，可将求解分为三步：

1. **确定 $n$ 所在数字的位数**，**记为 $digit$**：
      1. **循环执行 $n$ 减去一位数**、**两位数**、...**的数位数量 $count$**，**直至 $n \le count$ 时跳出**。
      2. **由于 $n$ 已经减去了一位数**、**两位数**、...、$(digit - 1)$**位数的数位数量 $count$**，**因而此时的 $n$ 是从起始数字 $start$ 开始计数的**。

![Picture2.png](/media/202202/2022-02-09_1741260.942468520063812.png)
   2. **确定 $n$ 所在的数字**，**记为 $num$**：
      1. **所求数位在从数字 $start$ 开始的第 $\frac{n - 1}{digit}$ 个数字中**（$start$ 为第 0 个数字），即

$$
         num = start + \frac{n - 1}{digit}
         $$

![Picture3.png](/media/202202/2022-02-09_1745320.31558270921165665.png)
   3. **确定 $n$ 是 $num$ 中的哪一数位**，**并返回结果**：
      1. **所求数位为数字 $num$ 的第 $\frac{n - 1}{digit}$ 位**（数字的首个数位为第 0 位）。

![Picture4.png](/media/202202/2022-02-09_1749000.4903168084894265.png)
3. 具体实例如下：

![](/media/202202/2022-02-09_1749560.8402380541484955.png)

![](/media/202202/2022-02-09_1750080.9277916893013155.png)

![](/media/202202/2022-02-09_1750250.8687465615429757.png)

## 3 参考代码

```java
/**
 * 剑指 Offer 44. 数字序列中某一位的数字
 * @param n 数字序列中的位数
 * @return  数字序列中第 n 位的数字
 */
public int findNthDigit(int n) {
    int digit = 1, res = 0;
    long start = 1, count = 9, num = 0;

//  1. 确定 n 所在数字的位数
    while (n > count) {
        n -= count;
        digit++;
        start *= 10;
        count = 9 * digit * start;
    }

//  2. 确定 n 所在的数字
    num = start + (n - 1) / digit;
    //  3. 确定 n 是 num 中的哪一数位
    res = Long.toString(num).charAt((n - 1) % digit) - '0';
    return res;
}
```

## 参考文献

1. [剑指 Offer 44. 数字序列中某一位的数字](https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof)。
2. [面试题 44. 数字序列中某一位的数字（迭代 + 求整 / 求余，清晰图解）](https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6)。