面试题 44：数字序列中某一位的数字.md

试题链接：57. 数字序列中某一位的数字 - AcWing题库

方法一：数学

• 思路：按位数来划分块，先找到第 n 位在哪个块，在看是这个块里哪个数的哪一位。一位数有 0 ~ 9 十个，两位数有 10 ~ 99 共 99 - 10 + 1 即 100 - 10 = 90 个数，三位数有 100 ~ 999 共 1000 - 100 的 900 个数，我们可以用一个式子得出每个块有多少个数，再乘以位数则得到了这个块一共有多少位，这样我们就可以确认第 n 位在哪个块上的哪一位，但是由于第一个区间中有个 0，故 base - base / 10 的计算方法不适应，我们排除 0 这种特殊情况，令第一个区间从 1 开始，则我们的 n 也改为从 1 开始，这样就不影响结果，原来是从 0 开始，区间左移一位后，第 0 位对应原来的第 1 位。当区间长度小于 n 时，我们不断将 n 减去区间长度，当减不了时，则当前区间 [base / 10, base - 1] 的第 n 位是答案，区间的每个数占 cnt 位，因此我们可以用 n / cnt 向上取整得到答案在区间的第几个数上，最后通过 (n - 1) % cnt 确认在这个数的哪个下标。
• 时间复杂度：O(logn)
• 空间复杂度：O(1)

class Solution {
public:
    int digitAtIndex(int n) {
        if (n == 0) return 0;
        
        // 让第一个区间是 [1, 9] 而不是 [0, 9]
        long long base = 10, cnt = 1;
        
        while ((base - base / 10) * cnt < n) {
            n -= (base - base / 10) * cnt;
            base *= 10;
            cnt++;
        }
        
        // [base / 10, base - 1] 区间的第 n 位数, 每个数占 cnt 位
        
        // 1. 找到在哪个数上, 需要向上取整确认需要多少个 cnt 位的数
        int d = base / 10 + (n + cnt - 1) / cnt - 1;
        
        // 2. 确定是在这个数的第几位, n 是从 1 开始的, 所以要 -1 后取模
        int p = (n - 1) % cnt;
        
        return to_string(d)[p] - '0';
    }
};