题目描述

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

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

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

样例

样例
输入：13

输出：1

算法1

(暴力枚举) $O(logn)$

C++ 代码

class Solution {
public:
    int digitAtIndex(int n) {
        if(n == 0) return 0;

        //1 算出n是位于几位数中
        long long cnt = 9, i = 1, base = 1;
        // int cnt = 9, i = 1, base = 1;
        // cout<<n<<endl;
        while(n > cnt * i){
            n -=  i * cnt;
            ++i;
            cnt *= 10;
            base *= 10;
            // cout<<n<<endl;
            // cout<<"base"<<base<<endl;  //会出现 int 越界错误

        }

        //2 计算是i位数的第几个数
        int c = (n + i - 1) / i;         //上取整
        // cout<<"n"<<n<<endl;
        int num = base + c - 1;         //算出这个数是几
        // cout<<"num: "<<num<<endl;
        int j = n % i;                  

        //3计算那一位数字是几；
        if(j == 0) return num % 10;
        for(int k = j; k < i ; ++k){
            num /=10;
        }
        return num % 10;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla