数字以 0123456789101112131415… 的格式作为一个字符序列,在这个序列中第 2 位(从下标 0 开始计算)是 2 ,第 10 位是 1 ,第 13 位是 1 ,以此类题,请你输出第 n 位对应的数字。
分析: 0-9 :共10个;
10-99 :共90个数据,每个数据2个数字,共有902个数字。
100-999:共900个数据,每个数据3个数字,共有9003个数字。
1000-9999:共9000个数据,每个数据4个数字,共9000*4个数字。
解法:
1,我们可以根据题目给的n来确定一个区间,来判断所在区间是几位数的区间。
2,用n减去区间开头数据来获得,来判断是区间的第几位数字。
3,用区间的第多少位除以区间是几位数(例如所在区间是4位数,那么就除以4),来获得能构成几个整的数据。
4,组成整的数据后可能会余下几个数字,我们根据余下几个数字来获取最后一个完整数据的第几位。
5,再第三步中,如果一个整的数据都凑不成,那么第4步中最后一个完整的数据就换成这个区间开头的数据。
6,如果第4步中余下的数字为0并且是在凑成几个完整的数据的情况下,我们直接返回最后一个完整数据的最后一位。
代码:
int findNthDigit(int n )
{
// write code here
if(n<10)
return n;
long long sum=10;
int i=90;
int j=2;
while((n-sum>=0))//确定区间
{
sum+=i*j;
i*=10;
j++;
}
sum=sum-(int)pow(10,j-2)*(j-1)*9;
int ret=0;
int rem=n-sum+1;//除去最高位后得到的数字
int N=rem/(j-1);//凑成几个这样位数的整数
int _rem=rem%(j-1);//凑不成完整整数的余数
if(N==0)
ret=(int)pow(10,(j-2));
else
ret=(int)pow(10,(j-2))+N-1;
if(_rem==0&&N!=0)
return ret%10;
return ((ret/((int)pow(10,(j-2)-_rem+1)))%10);
}