题目描述

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

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

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

样例

输入：13

输出：1

算法

(数位统计) $O(logn)$

首先我们知道的是，1 位数有 10 个，2 位数有 90 个，3 位数有 9 * 100 个，4 位数有 9 * 1000 个

注意：
1. 为了方便，从 1 开始计数，从 1 开始以 1 计数和从 0 开始以 0 计数的结果是一样的（除去 n = 0）
2. 一位数中先不考虑 0，那么一位数就变成 9 个

三步操作

1. 确定是几位数，比如是三位数
2. 确定是几位数的第几个数，比如是三位数的第 20 个数，即 100 + 20 - 1 = 119。
3. 确定属于那个数的第几位

时间复杂度

总的时间复杂度即三步操作的时间复杂度

1. int 的范围 $2*10^9$，所以最多是 10 位数，因此第一步操作的时间是 $O(1)$ 的
2. 第二步除法向上取整，也是 $O(1)$ 的
3. 第三步求是第几位数字是 $O(log_{10}n)$ 的
   在二进制表示中取某一位可以每次右移 1 位（即除以 2），所以是 $O(log_2n)$ 级别的，
   同理在十进制中取某一位可以每次右移 1 位（即除以 10），所以是 $O(log_{10}n)$ 级别的

C++ 代码

class Solution {
public:
    int digitAtIndex(int n) {
        // n ++ ; // 题目是从 0 开始计数，我们的思路是从 1 开始计数，所以 n 往后移一位
        // n -- ; // 先不考虑 0

        // i 表示几位数，s 表示 i 位数有几个，base 表示第 i 位数的第一个数是谁
        long long i = 1, s = 9, base = 1;

        // 1. 确定是几位数
        while (n > i * s)
        {
            n -= i * s;
            i ++ ;
            s *= 10;
            base *= 10;
        }
        // 循环结束 n 存的就是第 i 位数的第几位

        // 2. 确定是 i 位数的第几个数：(n + i - 1) / i，需要向上取整，如果有余数说明是下一个数
        // number 存的就是这个数
        int number = base + (n + i - 1) / i - 1;
        // 求余数（第几位），如果 r = 0 表示是最后一位（也就是 i，几位数就是几），如果 r = 1 表示是第一位 ... 依此类推
        int r = n % i ? n % i : i;
        // 3. 取出这一位
        for (int j = 0; j < i - r; j ++ ) number /= 10;
        // 如果是 1 位数，个位就是答案，如果是多位数，经过第 3 步处理，个位也就是答案
        return number % 10;
    }
};