題目描述

統計一個數字在排序數組中出現的次數。

• 0 <= 數組長度 <= 50000

題目樣例

示例

• 輸入: nums = [5,7,7,8,8,10], target = 8

• 輸出: 2

• 輸入: nums = [5,7,7,8,8,10], target = 6

• 輸出: 0

題目思考

1. 可以用小于 O(N)的時間復雜度得出結果嗎?
2. 可以做到 O(1) 空間復雜度嗎?

解決方案

思路

• 一個比較容易想到的思路是使用一個計數字典, 遍歷一遍數組統計每個數的出現次數, 最后返回 target 的次數. 但這樣時間和空間復雜度都是 O(N), 也用不上題目中數組是排序的這一條件
• 如何利用排序這一條件統計數字出現次數呢? 我們可以嘗試二分查找的思路, 分別找到該數字的左右邊界對應的下標, 然后次數就是 右邊界-左邊界+1 (數組存在該數字的情況下)
• 查找左邊界: 如果找到等于 target 的數時, 需要繼續往左找. 而如果數組中沒有等于 target 的數, 則直接返回 None, 此時就知道該數字的出現次數為 0 了, 無需繼續找右邊界
• 查找右邊界: 如果找到等于 target 的數時, 需要繼續往右找
• 注意可以將二分查找代碼整合到一個方法中, 傳入一個 flag 標記當前是找左邊界還是右邊界, 以減少代碼冗余
• 下面代碼對必要的步驟有詳細的解釋, 方便大家理解

復雜度

• 時間復雜度 O(logN): 二分查找兩次
• 空間復雜度 O(1): 只定義了幾個變量

代碼

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binarySearch(isleft):
            # 傳入flag isleft, 標記當前是查找左邊界還是右邊界
            s, e = 0, len(nums) - 1
            # 初始化結果為None
            res = None
            while s <= e:
                m = (s + e) >> 1
                if nums[m] == target:
                    if isleft:
                        # 當前查找的是左邊界, 更新結果為等于target的更小的下標, 同時向左繼續查找
                        res = m if res is None else min(res, m)
                        e = m - 1
                    else:
                        # 當前查找的是右邊界, 更新結果為等于target的更大的下標, 同時向右繼續查找
                        res = m if res is None else max(res, m)
                        s = m + 1
                elif nums[m] < target:
                    s = m + 1
                else:
                    e = m - 1
            return res

        left = binarySearch(True)
        if left is None:
            # 如果左邊界不存在, 則說明整個數組沒有target, 直接返回0
            return 0
        right = binarySearch(False)
        # 最終結果就是右邊界-左邊界+1
        return right - left + 1