题目描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。

在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。

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

样例

输入：13

输出：1

算法

(模拟)

为了可以更好地理解这个算法，我代入了1个实例，n = 1022，匹配到的数是377，对应它的第2位，也就是3后面的那个7，输出ans是7
1. 首先不断地对1022进行处理，也就是第1个while()循环做的事情，得到base = 100, i = 3, n = 833。那么得到的信息就是1022位数处于3位数的区间，那一位从100开始数，是第833位。
2. 第二步，我们就可以通过100和3和833这三个信息推出1022位数字，具体落脚在了哪个3位数上。
3. 我们来逆推下公式，比如377这个数，$(377 - 100 + 1) * 3$得到的就是100到377有多少位数字，结果是834。
4. 我们上面求出的n是833，834指的是377最后一位的位数。所以为了求出377，我们通过(n + (i - 1)) / i，从而求出来它具体在第几位。然后得出在100后面的第278位，最后(278 + 100 - 1) = 377。
5. 得到number后，我们通过833 % i的结果，如果能除尽，就是number的最后一位，也就是i位；不然就是number中从第1位算起的第n % i位(下标从1开始哦)。
6. 算出来r是2后，说明是377的第2位，也就是第1个7，我们让它除10，一次，除10的次数是[0 ~ i - r)
7. 处理后的number的个位就是要求的答案，我们返回的时候number % 10就ok。

时间复杂度

$O(log_{10}n)$
时间复杂度分3步：
1. 确定寻找的n处于几位数的范畴，1位数，2位数，还是3位数....这里的时度是$O(1)$。
2. 确定是i位数后，确定是i位数中的哪个，比如说4位数的第256个数，1000 + 256 - 1 = 1255，1255就是4位数的其中1个。这里的时度是$O(1)$，用到了除法。
3. 确定是哪个数以后(比如确定是1255这个数以后)，看看数字n是这个数的第几位，拿1255来举例子，是1还是2还是5还是5。这里是取余，时度是$O(1)$的，然后取出来是哪一位数，最多是10位，所以最多是10次操作，时间复杂度为$O(log_{10}n)$。

C++ 代码

class Solution {
public:
    int digitAtIndex(int n) 
    {
        long long i = 1, num = 9, base = 1;
        while(n > i * num)
        {
            n = n - i * num;
            i ++;
            num = num * 10;
            base = base * 10;
        }

        int number = base + (n + i - 1) / i - 1; 
        int r = n % i ? n % i : i; 
        for(int j = 0; j < i - r; j ++) number = number / 10;

        return number % 10;
    }
};