class Solution {
public:
    int digitAtIndex(int n) {
        //思路，对不同位数的数进行分类讨论，如12为2位数，2123为4位数，时间复杂度为logN
        long long i = 1,s = 9,base = 1;//i代表为几位数，s 代表该数有几个数，eg 1为数有9个，base
        //代表该位数的起始值，1位数起始值是1
        while(n > s * i){
            n -= s * i;
            i ++;
            s *= 10;
            base *= 10;
        }//该循环算出该数是几位数
        int number = base + (n + i - 1)/i - 1;  //求出该数是多少，eg 1235
        int r = n % i ? n % i : i;
        for(int j = 0;j < i - r;++j)    number /= 10;
        return number % 10;

    }
};