讨论/《图解算法数据结构》 - 剑指 Offer 44. 数字序列中某一位的数字/
《图解算法数据结构》 - 剑指 Offer 44. 数字序列中某一位的数字

c++

class Solution {
public:
    int findNthDigit(int n) 
    {
        if(n <= 9) return n;
        int idx = 1;
        long long digitNum = 9;
        //找到是第几位数,一位/二位/三位/...
        while(digitNum < n)
        {
            digitNum += (idx+1)*9*pow(10,idx);
            idx += 1;
        }
        idx -= 1;
        digitNum -= (idx+1)*9*pow(10,idx);
        n = n - digitNum;
        //找到该数字
        int a = n / (idx + 1);
        int b = n % (idx + 1);
        if(!b)
        {
            int temp = pow(10,idx)+a-1;
            return func(temp)[idx];
        }
        else
        {
            int temp = pow(10,idx)+a;
            return func(temp)[b-1];
        }
        return -1;
    }

private:
    //丢进数组里直接找相应的值
    deque<int> func(int num)
    {
        deque<int> deq;
        while(num)
        {
            deq.push_front(num % 10);
            num /= 10;
        }
    
        return deq;
    }
};