问题

将所有整数按序排列格式化为字符串，求该字符串的第n位是哪个数字

算法：数学规律

规律题，先确定第n位数在哪个范围，在确定具体的数和位，然后转成字符串输出结果即可

时间复杂度

$O(logn)$, 找到具体的数只需要logn次循环，将具体的数转化为字符串也只需要logn

代码

class Solution {
public:
    int findNthDigit(int n) {
        if(n < 10) return n;
        n -= 10;

        typedef long long LL;
        LL dig = 2, cnt = 90; // dig是位数，cnt是dig位数的数字数量
        while(n > dig * cnt){
            n -= dig *cnt;
            dig ++;
            cnt *= 10;
        }

        int num = pow(10,dig-1) + n / dig; // 求具体的是哪个数
        int d = n % dig; // 这个数的第几位
        return to_string(num)[d] - '0';
    }
};