本文共 1223 字,大约阅读时间需要 4 分钟。
题目:
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:3Output:3
Example 2:
Input:11Output:0Explanation: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
注意:
n是正数并且范围在32位带符号整数之内(n < 2^31)
解题思路:
将整数序列划分为下列区间:1 1-92 10-993 100-9994 1000-99995 10000-999996 100000-9999997 1000000-99999998 10000000-999999999 100000000-99999999
然后分区间求值即可。
方法一:性能56ms
class Solution(object): def findNthDigit(self, n): """ :type n: int :rtype: int """ for i in range(9): d = 9 * pow(10, i) if n <= d * (i + 1): break n -= d * (i+1) n -= 1 return int(str(pow(10, i) + n/(i+1))[n % (i+1)])
方法二:性能38ms
class Solution(object): def findNthDigit(self, n): """ :type n: int :rtype: int """ N=1 while n>0: r= 9* 10**(N-1)*N if n>r: n-=r N+=1 else: number= 10**(N-1) + (n-1)/N return int(str(number)[(n-1)%N])
转载地址:http://jgcrj.baihongyu.com/