算法

$O(logN)$

数理概率题，分析数字规律，个位数有10个，2位数90个，三位数900个，四位数9000个
采用以下几个步骤：

1. 定位是几位数的数字
2. 定位到是哪个数值
3. 定位这个数值的某位

时间复杂度

参考文献

C++ 代码

int digitAtIndex(int n) {
    long long i = 1,s = 9,base = 1;//i表示是几位数字，s表示几位数字的个数，base表示几位数字的起始
    //比如，i=2，表示的是两位数，10-99，s表示有90个（99-10+1），base为10，两位数起始为10
    while(n>i*s)
    {
        n -= i *s;
        i++;
        s *= 10;
        base *= 10;
    }
    //现在的n表示在i位数中第几位，换算成真正的数值，需要让n/i上取整等价于n+i-1
    int number = base + (n+i-1)/i-1;
    int r = n % i ==0 ? i : n % i;//r表示n是number的第几个数字，如果可以整除i说明是最后一个，即第i位，否则是n%i
    for(int j = 0;j<i-r;j++) number /= 10;//求数的第i - r位，取出第i - r位
    return  number % 10;
}

```