【leetcode刷題】T199-第N個數字

• 2019 年 11 月 24 日
• 筆記

木又連續日更第62天（62/100）

木又的第199篇leetcode解題報告

數學類型第15篇解題報告

leetcode第400題：第N個數字

https://leetcode-cn.com/problems/nth-digit

【題目】

在無限的整數序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 個數字。

注意: n 是正數且在32為整形範圍內 ( n < 231)。

示例 1:  輸入:  3  輸出:  3    示例 2:  輸入:  11  輸出:  0  說明:  第11個數字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。

【思路】

本題的第n個數，是將所有數排成一排，按位選取的一個數，概述肯定小於10。

我們可以找到規律：

小於10的一位數，共有9個；

小於100的兩位數，共有90個；

小於1000的三位數，共有900個；

……

因此，不斷循環判斷：

i = 0  while n > 0:      n -= (i+1) * 9 * (10 ** i)      i += 1

當n退出循環，則滿足條件的數在9 * (10 ** (i-1)) 到9 * (10 ** i)之間。

怎麼判斷具體是哪一個數呢？

自然數為9 * (10 ** (i-1)) + (n – 1) // (i + 1)

該自然數的第(n-1) % (i+1)位。

（i+1表示自然數的位數）

【代碼】

python版本

class Solution(object):      def findNthDigit(self, n):          """          :type n: int          :rtype: int          """          # 一位數 9          # 兩位數 (99-9) * 2          # 三位數 900 * 3          if n < 10:              return n            x = 1          n -= 9          while n > 0:              n -= (x + 1) * 9 * (10 ** x)              x += 1          x -= 1          n += (x+1) * 9 * (10 ** x)            res = 10 ** x + (n-1) // (x+1)          p = (n-1) % (x+1)          print(res, p)          return int(str(res)[p])

前一篇文章：T198-整數替換