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%的用户