【leetcode刷题】T199-第N个数字
木又连续日更第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-整数替换
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-11-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读