剑指 Offer 44. 数字序列中某一位的数字
1 题目描述
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例1：
输入: n = 3
输出: 3
示例2：
输入: n = 11
输出: 0
2 思路
个位一共有(9-1+1)*1 = 9位数(0不算)，十位有(99-10+1)*2 = 2*9*10 = 180, 百位有(999-100+1)*3 = 3*9*100 = 2700……因而，设某个数为i，其位数为j，则从1~i的序列一共的数字位数n(包含其本身)为：
上边的式子中第一项实际上就是计算位数小于j的数字的数字位数总和，而后边一项则是求位数为j的第一个数到i之间的数字的数字位数总和。
因此，直接的办法就是先求前边那一项来确定目标数的位数，即用一个变量cnt来记录前边一项的结果，当cnt + j*9*pow(10, j-1)> n时，说明数字位数为j. 然后利用n - cnt来确定第二项，进而再确定目标数的值.剩余数字位数除以当前的数字有多少位即可得到目标数，即(n-cnt)/j。最后确定序列中第n位数字是目标数的哪一位，返回对应位即可。注意，计算目标数时，其公式应该为：
切记不能少-1，因为cnt中并没有包括$10^{j-1}$这一个数字。
class Solution {
public:
int findNthDigit(int n) {
if(n < 10) return n;
int cnt = 0, j = 1;
// 计算目标数的位数
for( ; cnt+j*9*pow(10, j-1) < n; ++j){
cnt += j*9*pow(10, j-1);
}
// 计算剩余位数
cnt = n - cnt;
// 计算目标数
int num = pow(10, j-1) + cnt/j -1;
// 计算对应位上的数
if(cnt % j){
num += 1;
return num / (int)pow(10, j-(cnt%j)) % 10;
}
return num % 10;
}
};
