解法一： 一个几乎纯数学的解法

numbers:   1,...,9, 10, ..., 99, 100, ... 999, 1000 ,..., 9999, ...

# of digits:   9     +  90*2   +  900*3 + 9000*4 + ...

利用这个公式可以很容易的求出来Nth digit出现在一个几位数上。假设出现在一个4位数上。那么我们应该从1000的第一个1开始往后数 n - (9 + 90*2 + 900*3)个digits。那么第n个digits应该出现在那个4位数上呢？可以用L17算出来这个数是1000后面的第几个自然数， e.g. 5。res为最后剩余的digits的个数，这个res<=4。那么我们应该找 '1005' 中的第res-1个digit。

1 class Solution(object): 2     def findNthDigit(self, n): 3         """ 4         :type n: int 5         :rtype: int 6         """ 7         sum = 0 8         i = 1 9         while n > sum + i*9*10**(i-1):10             sum += i*9*10**(i-1)11             i += 112         start = 10**(i-1) 13         step = (n - sum - 1)//i14         res = n - sum - step*i15         return int(str(start + step)[res-1])