题目

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的指数也就很好理解了。
如果仍然不好理解，烦请读者“躬行”，做一下简要的计算即可。