44. a digit in a sequence of digits

The finger of the sword Offer 44. A number in a sequence of numbers

Ideas ： iteration + Integer / Seeking remainder

1. determine n Number of digits
2. determine n The number in which
3. determine n yes num Which digit of

1. determine n Number of digits

Loop execution n Subtract one digit , Double digits ,… The number of count, until n<=count Jump out of .

2. Determine the number where the desired digit is located

$num=start+(n-1)//digit$

3. Determine what is required num Which digit of

s=str(num)
res=s[(n-1)%digit]-'0';

class Solution {
public:
    int findNthDigit(int n) {
        int digit=1;
        long start=1;
        long count=9*digit*start;
        while(n>count){
            n-=count;
            digit++;
            start*=10;
            count=long(9)*digit*start;
        }

        int num=start+(n-1)/digit;
        int res=to_string(num)[(n-1)%digit]-'0';
        return res;
    }
};

Time complexity O(logn)

Spatial complexity O(logn) Convert numbers to strings , Occupy O(logn) Extra space