给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …] 中找出并返回第 n 位上的数字。

示例 1：

**输入：**n = 3
**输出：**3

示例 2：

**输入：**n = 11
**输出：**0
**解释：**第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是 0 ，它是 10 的一部分。

提示：

1 <= n <= 2(31) - 1

我们可以先找出第n个数字是在几位数中，再找出是第几个数，最后找出是哪一位

一个变量 start 表示从start开始的第n个数字

num表示几位数，maxN表示一共多少个数字，例如一位数共9个，两位数共（99-9）*2

三位数共（999-99）*3个

n每次减去当前num位数的总数字，直到不足maxN

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public : int findNthDigit(int n) {
        int num = 1;
        long long int maxN = 9;
        long long int start = 0;
        while ((long long)n > maxN) {
            num++;
            n -= maxN;
            start = start * 10 + 9;
            maxN = (start * 9 + 9) * num;
        }

        int no;
        if (n % num == 0)
            no = start + n / num;
        else
            no = start + n / num + 1;
        int count = n % num == 0 ? 0 : num - n % num;
        while (count != 0) {
            count--;
            no /= 10;
        }
        return no % 10;
    }
};