算法1

$O(1)$

第n位其实就是n+1位
分别求出不同位数的所有数字的长度和
然后定位到对应的数字，对应的余数

C++ 代码

class Solution {
public:
    int digit(int bit,int n,int level){

        int a = 0;
        for(int i=0;i<(level-bit)+1;i++){
            a = n % 10;
            n/=10;
        }
        return a;
    }
    int digitAtIndex(int n) {
        //1bit: 10               0-9
        //2bit: (99-10+1) * 2    10 - 99
        //3bit: (999-100)*3      100-999
        if (!n) return 0;
        if (n==INT_MAX) return 2;
        n++;
        int m = INT_MAX;
        long look_table[100];
        memset(look_table,0,sizeof(look_table));

        for(int i=1;i<10;i++){
            if (i==1) {
                look_table[i] = 10;
                continue;
            }
            long a = pow(10,i);

            long b = (a-int(pow(10,i-1)) ) * i + look_table[i-1] ;

            look_table[i] = b;
            //  cout<<look_table[i]<<endl;
            // if (a > m || b > m) break;

        }
        int level = 0;
        for(int i=1;i<=9;i++){
            // cout<<i<<endl;
            if (look_table[i] > long(n)){
                level = i;
                break;
            }
            else if(look_table[i] == long(n)){
                level = i+1;
                return 9;
            }
        }
        // cout<<level<<endl;
        if (n<10) return --n;
        n-=look_table[level-1];
        // cout<<"111"<<endl;
        // cout<< n<<endl;
        int res = n/(level);
        int bias = n%(level);
        // cout<<look_table[level-1]<<endl;
        //  cout<<res<<" "<<bias<<endl;
        if (res == 0 && bias ==0) return 9;

        if(bias>0){
            return digit(bias,int(pow(10,level-1))+res,level);
        }
        else{
            return digit(level,int(pow(10,level-1))+res-1,level);
        }

        return 0;
    }
};