题目
数字以0123456789101112131415…的格式序列化到一个字符序列中。
在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数求任意位对应的数字。
样例
输入：13
输出：1

解法：数位统计

1. 确定n对应一个几位数
2. 确定n对应几位数的第几个，也就是n具体对应哪一个数
3. 确定n对应这个数的第几位

时间复杂度O(logn)，空间复杂度O(1)

class Solution {
public:
    int digitAtIndex(int n) {
        int m = n;
        // i：几位数，base：几位数的开头，cnt：几位数一共有多少个，sum：一共有多少个数
        long long i = 1, base = 1, cnt = 9, sum = 1;    
        while (m > i * cnt) {
            m -= i * cnt;
            sum += i * cnt;
            i++;
            cnt *= 10;
            base *= 10;
        }
        int num = base + (n - sum) / i;    // 具体是哪一个数，向下取整，所以整除是正好，不然是前一个
        int p = n - sum - (num - base) * i;    // 数字的第几位
        for (int j = 0; j < i - p - 1; j++) num /= 10;
        return num % 10;
    }
};