LeetCode如何找出數(shù)字序列中某一位的數(shù)字

題目描述

數(shù)字以 0123456789101112131415…的格式序列化到一個字符序列中。在這個序列中，第 5 位（從下標 0 開始計數(shù)）是 5，第 13 位是 1，第 19 位是 4，等等。

請寫一個函數(shù)，求任意第 n 位對應的數(shù)字。

• 0 <= n < 2^31

題目樣例

示例

• 輸入：n = 3

• 輸出：3

• 輸入：n = 11

• 輸出：0

題目思考

1. 能否找到什么規(guī)律?

解決方案

思路

• 觀察序列本身:
• 0~9 只占 1 位, 共 10 個
• 10~99 占 2 位, 共 90 個
• 100~999 占 3 位, 共 900 個
• 1000~9999 占 4 位, 共 9000 個
• ...
• 為了保持一致, 我們可以將 1 位的時候改成從 1 開始, 把 n=0 作為特殊情況, 這樣 1 位也只有 9 個, 即 1~9
• 這樣我們就很容易發(fā)現(xiàn)規(guī)律, 假設當前位數(shù)是 le:
• 每一位的開始值 start 是                  pow(10, le-1)
• 每一位的數(shù)字數(shù)目是                  9*start
• 每一位的字符總數(shù)則是                  9*start*le (因為每個數(shù)字有 le 個字符)
• 所以我們可以逐漸增加位數(shù), 統(tǒng)計當前總共的字符個數(shù)
• 假設 le 位數(shù)下的字符總數(shù)是 cnt, le+1 下的字符總數(shù)是 nextcnt, 那么如果 n 在                 [cnt, nextcnt)范圍內(nèi), 那就說明 n 落在的數(shù)字一定有 le 位
• 這樣一來, 我們只需要定位 n 具體對應到的數(shù)字, 以及所在數(shù)字的第幾位即可
• 而由于每個數(shù)字占有 le 位, 所以 n 對應的數(shù)字就是                 start+(n-cnt)/le, 而具體 n 是在該數(shù)字的第幾位, 則是                 (n-cnt)%le
• 下面的代碼對必要步驟有詳細的解釋, 方便大家理解

復雜度

• 時間復雜度                 O(logN)
• 只需要按位數(shù)遍歷即可, n 的位數(shù)是 logN
• 空間復雜度                 O(1)
• 只使用了常數(shù)個變量

代碼

class Solution:
    def findNthDigit(self, n: int) -> int:
        if n == 0:
            return 0
        # 初始化計數(shù)值為1, 因為start最開始是1, 此時已經(jīng)有1個字符了
        cnt = 1
        # 初始化位數(shù)為1位
        le = 1
        while n >= cnt:
            # 求當前位數(shù)下的start
            start = 10**(le - 1)
            # 求當前位數(shù)+1情況下的字符總數(shù)
            nexcnt = cnt + 9 * start * le
            if n <= nexcnt:
                # 當前n落在范圍內(nèi), 找對應的數(shù)字和該數(shù)字中n對應的位(偏移量)
                i, offset = divmod(n - cnt, le)
                num = start + i
                # 將數(shù)字轉成字符串, 其偏移量下標對應的位即為所求
                return int(str(num)[offset])
            # 更新字符總數(shù), 同時位數(shù)加1, 繼續(xù)循環(huán)
            cnt = nexcnt
            le += 1