剑指 Offer 44. 数字序列中某一位的数字 - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:17
浏览次数:4
分类:技术文章
本文共 1602 字,大约阅读时间需要 5 分钟。
题目难度: 中等
今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
数字以 0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第 5 位(从下标 0 开始计数)是 5,第 13 位是 1,第 19 位是 4,等等。
请写一个函数,求任意第 n 位对应的数字。
- 0 <= n < 2^31
题目样例
示例
-
输入:n = 3
-
输出:3
-
输入:n = 11
-
输出:0
题目思考
- 能否找到什么规律?
解决方案
思路
- 观察序列本身:
- 0~9 只占 1 位, 共 10 个
- 10~99 占 2 位, 共 90 个
- 100~999 占 3 位, 共 900 个
- 1000~9999 占 4 位, 共 9000 个
- …
- 为了保持一致, 我们可以将 1 位的时候改成从 1 开始, 把 n=0 作为特殊情况, 这样 1 位也只有 9 个, 即 1~9
- 这样我们就很容易发现规律, 假设当前位数是 le:
- 每一位的开始值 start 是
pow(10, le-1)
- 每一位的数字数目是
9*start
- 每一位的字符总数则是
9*start*le
(因为每个数字有 le 个字符)
- 每一位的开始值 start 是
- 所以我们可以逐渐增加位数, 统计当前总共的字符个数
- 假设 le 位数下的字符总数是 cnt, le+1 下的字符总数是 nextcnt, 那么如果 n 在
[cnt, nextcnt)
范围内, 那就说明 n 落在的数字一定有 le 位 - 这样一来, 我们只需要定位 n 具体对应到的数字, 以及所在数字的第几位即可
- 而由于每个数字占有 le 位, 所以 n 对应的数字就是
start+(n-cnt)/le
, 而具体 n 是在该数字的第几位, 则是(n-cnt)%le
- 下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度
O(logN)
- 只需要按位数遍历即可, n 的位数是 logN
- 空间复杂度
O(1)
- 只使用了常数个变量
代码
class Solution: def findNthDigit(self, n: int) -> int: if n == 0: return 0 # 初始化计数值为1, 因为start最开始是1, 此时已经有1个字符了 cnt = 1 # 初始化位数为1位 le = 1 while n >= cnt: # 求当前位数下的start start = 10**(le - 1) # 求当前位数+1情况下的字符总数 nexcnt = cnt + 9 * start * le if n <= nexcnt: # 当前n落在范围内, 找对应的数字和该数字中n对应的位(偏移量) i, offset = divmod(n - cnt, le) num = start + i # 将数字转成字符串, 其偏移量下标对应的位即为所求 return int(str(num)[offset]) # 更新字符总数, 同时位数加1, 继续循环 cnt = nexcnt le += 1
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107672020 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月09日 17时04分58秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
1元钱的超低成本单芯片USB单片机方案
2019-04-29
单片机/树莓派扩展双串口(TTL和RS485)
2019-04-29
JAVA(android)提取WIFI客流探针MAC地址源码
2019-04-29
基于CH568芯片的SATA电子盘方案
2019-04-29
linux下C语言判断网络是否连接
2019-04-29
STM32Cube_FW_F4_V1.17 F4固件包百度网盘下载
2019-04-29
猿来绘Java-35-线程的同步(生产者和消费者问题)
2019-04-29
猿来绘Java-36-解决线程安全问题
2019-04-29
猿来绘Java-37-ReentrantLock解决线程安全问题
2019-04-29
猿来绘Java-38-生产者消费者模型
2019-04-29
猿来绘Java-39-JDK8的新日期时间类
2019-04-29
猿来绘Java-40-比较器(Comparable 接口与 CompareTo方法)
2019-04-29
猿来绘Java-41-源码分析String对象的数组的排序(JDK1.8)
2019-04-29
猿来绘Java-42-枚举类的使用
2019-04-29
猿来绘Java-43-初步认识注解
2019-04-29
猿来绘Java-44-自定义注解和元注解
2019-04-29
猿来绘Java-45-JDK8新特性可重复注解和类型注解
2019-04-29
猿来绘Java-46-Collection接口及其方法
2019-04-29
猿来绘Java-47- foreatch 增强for循环
2019-04-29
2021/4/27课堂总结和作业
2019-04-29