劍指offer：數(shù)字序列中某一位的數(shù)字

題目描述
數(shù)字以0123456789101112131415…的格式序列化到一個字符序列中。在這個序列中，第5位（從0開始計數(shù)）是5，第13位是1，第19位是4，等等。請寫一個函數(shù)，求任意第n位對應(yīng)的數(shù)字。

# -*- 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開始遍歷所有整數(shù)，然后統(tǒng)計已經(jīng)出現(xiàn)了多少位數(shù)字，直到直到所求下標的數(shù)字。這樣
    做的話效率太低。

    如果我們能先確定所求下標的數(shù)字是屬于幾位小數(shù)的，即先確定答案位于三位數(shù)還是四位數(shù)還是五位數(shù)的數(shù)
    字中，然后再在這個位數(shù)段中確定具體是哪個數(shù)字，最后在這個數(shù)字中確定是哪一位，這樣就可以大大降低
    復(fù)雜度。
    """
    if index < 0:
        return -1
    # 所求的位置屬于幾位數(shù)，先從個位開始
    digit = 1
    while True:
        # 如果確定了所求位置屬于幾位數(shù)了，就進一步求具體的數(shù)字
        if index <= countOfDigit(digit):
            return findDigitWithinRange(digit, index)
        # 否則跳過這個n位數(shù)
        index -= countOfDigit(digit) * digit
        digit += 1

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

if __name__ == '__main__':
    main()