【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-整数替换