400.Nth Digit

400.Nth Digit

难度:Easy

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

Input:
3

Output:
3
Example 2:

Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

先确定位数范围(1位数、2位数。。。)，然后找到对应值。

class Solution {
public:
    int findNthDigit(int n) {
        if(n<10) return n;
        int start=9;
        int len=1;
        int res=9;
        while(true){
            long int tmp= start+9*(len+1)*pow(10,len);
            len++;
            if(tmp> n)break;
            start=tmp;
            res+=9*pow(10,len-1);
        }
        if(start ==n) return 9;
        n-=start;
        int quo=n/len;
        int rem=n%len;
      //  cout<<start<< " "<<n<<endl;
      //  cout<<quo<<" " <<rem<<endl;
      //  cout<<len<<" " <<start<<endl;
        if(rem==0)
            return (res+quo)%10;
        else
        {
            n=res+quo+1;
       //     cout<<n<<endl;
            return to_string(n)[rem-1]-'0' ;
        }

    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户 内存消耗 :8.3 MB, 在所有 C++ 提交中击败了80.51%的用户