题目描述

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

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

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

样例

输入：13

输出：1

时间复杂度

O(log(n))

参考文献

C++ 代码

class Solution {
public:
    int digitAtIndex(int n) {
        long long i = 1, s = 9, base = 1;//i:表示几位数，s:第i 位数一共有s个数，base：表示i位数的第一个数
        //1、先求出是一个几位数
        while(n > i * s){
            n -= i * s;
            i++;
            s *= 10;
            base *= 10;
        }
        //2、再求出是哪一个数
        int number = base + (n + i - 1) / i - 1;
        //3、最后求出是该数的第几位
        int r = n % i? n % i: i;
        for(int j = 0; j < i - r; j++) number /= 10;
        return number % 10;
    }
};