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

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

# -*- 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/SysuJaycedef countOfDigit(digit):    return 9 * 10 ** (digit - 1) if digit > 1 else 10def 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 += 1def main():    print(digitAtIndex(21))if __name__ == '__main__':    main()