剑指offer:数字序列中某一位的数字

题目描述
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从0开始计数)是5,第13位是1,第19位是4,等等。请写一个函数,求任意第n位对应的数字。

10年积累的网站设计制作、做网站经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站设计后付款的网站建设流程,更有花山免费网站建设让你可以放心的选择与我们合作。

# -*- coding: utf-8 -*-
# @Time         : 2019-07-09 22:51
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : digitAtIndex.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

def countOfDigit(digit):
    return 9 * 10 ** (digit - 1) if digit > 1 else 10

def findDigitWithinRange(digit, index):
    if digit == 1:
        number = 0
    else:
        number = 10 ** (digit - 1)
    number += index // digit
    remainder = index % digit
    return str(number)[remainder]

def digitAtIndex(index):
    """
    最直观的做法就是从0开始遍历所有整数,然后统计已经出现了多少位数字,直到直到所求下标的数字。这样
    做的话效率太低。

    如果我们能先确定所求下标的数字是属于几位小数的,即先确定答案位于三位数还是四位数还是五位数的数
    字中,然后再在这个位数段中确定具体是哪个数字,最后在这个数字中确定是哪一位,这样就可以大大降低
    复杂度。
    """
    if index < 0:
        return -1
    # 所求的位置属于几位数,先从个位开始
    digit = 1
    while True:
        # 如果确定了所求位置属于几位数了,就进一步求具体的数字
        if index <= countOfDigit(digit):
            return findDigitWithinRange(digit, index)
        # 否则跳过这个n位数
        index -= countOfDigit(digit) * digit
        digit += 1

def main():
    print(digitAtIndex(21))

if __name__ == '__main__':
    main()

本文名称:剑指offer:数字序列中某一位的数字
本文路径:http://myzitong.com/article/gscsei.html