每日一題 – 劍指 Offer 53 – I. 在排序數組中查找數字 I

• 2020 年 7 月 5 日
• 筆記
• 數據結構與演算法

題目資訊

• 時間： 2019-07-04

• 題目鏈接：Leetcode

• tag：二分查找 哈希表

• 難易程度：簡單

• 題目描述：

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

示例1:

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

示例2:

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

注意

1. 0 <= 數組長度 <= 50000

解題思路

本題難點

排序數組中查找數字，性能最優。

具體思路

排序數組中的搜索問題，首先想到 二分法 解決。

排序數組 nums 中的所有數字 target 形成一個窗口，記窗口的 左 / 右邊界 索引分別為 left 和 right ，分別對應窗口左邊 / 右邊的首個元素。

統計數字 target 的出現次數，可轉化為：使用二分法分別找到 左邊界 left 和 右邊界 right ，易得數字 target 的數量為 right−left−1 。

• 計算中點 m=(i+j)/2（向下取整）
• 若 nums[m]<target ，則 target 在閉區間 [m+1,j] 中，因此執行 i=m+1；
• 若 nums[m]>target ，則 target 在閉區間 [i,m−1] 中，因此執行 j=m−1；
• 若 nums[m]=target ，則右邊界 right 在閉區間 [m+1,j] 中；左邊界 left 在閉區間 [i,m−1] 中。
  • 若查找 右邊界 right ，則執行 i=m+1 ；（跳出時 i指向右邊界）
  • 若查找 左邊界 left ，則執行 j=m−1 ；（跳出時 j指向左邊界）

提示：查找完右邊界後，可用 nums[j]=j 判斷數組中是否包含 target ，若不包含則直接提前返回 0 ，無需後續查找左邊界。查找完右邊界後，左邊界 left一定在閉區間 [0,j] 中，因此直接從此區間開始二分查找即可。

程式碼

class Solution {
    public int search(int[] nums, int target) {
        // 搜索右邊界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若數組中無 target ，則提前返回
        if(j >= 0 && nums[j] != target) return 0;
        // 搜索左邊界 right
        i = 0; 
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }
}

複雜度分析：

• 時間複雜度 O(logN) ： 二分法為對數級別複雜度。
• 空間複雜度 O(1) ：幾個變數使用常數大小的額外空間。

其他優秀解答

解題思路

直接遍歷排序數組，計數。

程式碼

class Solution {
    public int search(int[] nums, int target) {
        int count = 0;
        for(int num : nums){
            if(num == target){
              count++;
            }
        }
        return count;
    }
}