题目
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,3,...求第n位的数字是什么，这个序列第n位不就是第几个数字吗。其实题目中让求第n个数字，可以理解为，1,2,3...是一个字符串"123456789011121314..."依次类推，不超过最大的int型数。这样理解，第n个数即是求这个字符串序列中第n位的数字是什么。
理解题意之后，即有了一个想法，求第n位，先要判断这个n在哪个范围里面，然后在根据这个范围找到第n位是哪一个数字，再取余找到第几位（个、十、百...），即得到。
范围 位数 数量 单数字位数 单数字范围
1-9 1 9 9*1=9 1-9
10-99 2 90 90*2=180 10-189
100-999 3 900 900*3=2700 190-2889
1000-9999 4 9000 9000*4=36000 2890-38889
10000-99999 5 90000 90000*5=450000 38890-488889
上表中例举了数字和范围、位数、数量、单数字位数和范围之间的关系，可以根据位数来确定其它，但是要注意边界的处理。
代码（C语言）
int findNthDigit(int n) {
// confirm scope
int digit = 1;
int remain = 0;
int tempN = n;
while (true) {
remain = tempN - 9 * pow(10, digit - 1) * digit;
if (remain <= 0) {
remain = tempN;
break;
}
++digit;
tempN = remain;
}
// calculate the number
int theNum = (remain - 1) / digit + pow(10, digit - 1);
int pos = (remain - 1) % digit;
int nThDigit = theNum / (int)pow(10, digit - pos - 1) % 10;
return nThDigit ;
}
remain在while循环中保存着偏移值，如果小于0，则当前的位为存在的区间，此时tempN是上一次运算的结果，因此将其赋给remain来为下面的位数计算做准备。
theNum为准确的第几个数，remain-1在这里表示偏移要从0开始计算。另外，nThDigit的计算是从0,1,2,3逆向的，因此需要从高位往低位取，pow的指数也就很好理解了。
如果仍然不好理解，烦请读者“躬行”，做一下简要的计算即可。
