LeetCode如何找出数字序列中某一位的数字

发布时间:2021-12-15 14:16:29 作者:小新
来源:亿速云 阅读:110

这篇文章将为大家详细讲解有关LeetCode如何找出数字序列中某一位的数字,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

题目描述

数字以 0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第 5 位(从下标 0 开始计数)是 5,第 13 位是 1,第 19 位是 4,等等。

请写一个函数,求任意第 n 位对应的数字。

  • 0 <= n < 2^31
             

题目样例

示例

  • 输入:n = 3

  • 输出:3

  • 输入:n = 11

  • 输出:0

             

题目思考

  1. 能否找到什么规律?
             

解决方案

             

思路

  • 观察序列本身:
    • 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 个字符)
  • 所以我们可以逐渐增加位数, 统计当前总共的字符个数
  • 假设 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
         

关于“LeetCode如何找出数字序列中某一位的数字”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

推荐阅读:
  1. 剑指offer:数字序列中某一位的数字
  2. Java怎样找出数组中重复的数字

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:Qt for Android开发实例分析

下一篇:如何分析vue保存自动格式化换行

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》