成都创新互联网站制作重庆分公司

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

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

沙依巴克网站制作公司哪家好,找成都创新互联公司!从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设公司等网站项目制作,到程序开发,运营维护。成都创新互联公司于2013年开始到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联公司

题目描述

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


当前标题:LeetCode如何找出数字序列中某一位的数字
文章转载:http://cxhlcq.com/article/jejhid.html

其他资讯

在线咨询

微信咨询

电话咨询

028-86922220(工作日)

18980820575(7×24)

提交需求

返回顶部