第 N 位数字

给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位数字。

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

提示：

1 < = n < = 2 31 − 1 1 <= n <= 2^{31} - 1 1<=n<=231−1

class Solution {
   
public:
    int findNthDigit(int n) {
   
        int weishu = 1, sum = 1;
        while (n > (long long)9 * weishu * sum){
   
            n -= 9 * weishu * sum;
            weishu++;
            sum *= 10;
        }
        int cnt = (n - 1) / weishu + sum;
        int ans = 0;
        for (int i = (n - 1) % weishu; i < weishu;i++){
   
            ans = cnt % 10;
            cnt /= 10;
        }
        return ans;
    }
};

思路:

n=11，其实是1234567891011…字符串第11个，就是0

已知 x x x 位数共有 9 × 1 0 x − 1 9 \times 10^{x - 1} 9×10x−1个，所有 x x x 位数的位数之和是 x × 9 × 1 0 x − 1 x \times 9 \times 10^{x - 1} x×9×10x−1

使用 weishu 和 sum 分别表示 当前遍历到的位数 和 当前位的权重( 1 0 i 10^i 10i)，cnt是含有所找数字的那个数， 整个数列的第一个数是1，从低位向高位移动扫描，根据离末位的偏移量找到所找的数字。