題目描述

數字以 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