题目要求
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。请写一个函数,求任意第n位对应的数字。
思路
如果小于10,直接返回n就好了,这里面有一个规律10-99有9102个数字,100-999有91010*3个数字,以此类推,我们通过这个规律可以计算出是几位数的数字中找,用n减去之前计算过的组的总个数,可以得到在某一组中,我们要找这个组中的第几个数字,再计算是第几个某位数,计算出是某位数中的第几个数字(0,1,2),通过是第几个某位数计算出是哪一个具体的数字,通过数字中的第几位数,可以计算出是第几个数。
代码实现
class Solution {
public:
int findNthDigit(int n) {
if (n < 10)
{
return n;
}
int count = 1;
long sum = 9;
while (n >= sum)
{
n = n - sum;
sum = (sum / count) * 10 * (count + 1);
count++;
}
//n是当前这个等级里的第多少个数字
n--;
int target = n % count;//第几个
int group = n / count;//第多少个组
sum = 1;
int deng = count - 1;
while (--count)
{
sum *= 10;
}
sum = sum + group;//sum是具体的数字
int idx = deng - target;//数字的下标
while (idx)
{
idx--;
sum /= 10;
}
sum %= 10;
return sum;
}
};