跟着姚桑学算法-数字序列中某一位的数字

题. 数字序列中某一位的数字

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

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

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

数据范围
0≤ 输入数字 ≤2147483647

样例

输入：13

输出：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(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。

复杂度分析：

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(log10n)。

C++代码实现：

class Solution {
public:
    int pow10(int x){
        int res=1;
        for(int i=0;i<x;i++){
            res*=10;
        }
        return res;
    }
    int digitAtIndex(int n) {
        if(n<10){
            return n;
        }

        int m=n-9;
        long long k=2;
        while(m>9*k*pow10(k-1)){
            m-=9*k*pow10(k-1);
            k++;
        }
        //t---第t个k位数
        int t=m/k;
        int s=m%k;
        int num=pow10(k-1);
        num+=t;
        if(s==0){
            return (num-1)%10;
        }
        else{
            for(int i=0;i<k-s;i++){
                num/=10;
            }
            return num%10;
        }
    }
};