在排序數組中查找數字 I（二分法）+讀1

目錄

• 1 題目描述
• 2 解題（Java）
• • 2.1 解題思路
  • 2.2 代碼
• 3 複雜性分析

1 題目描述

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

示例 1:

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

輸出: 2

示例 2:

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

輸出: 0

限制：

0 <= 數組長度 <= 50000

2 解題（Java）

2.1 解題思路

1. 本題要求統計數字 target的出現次數，可轉化為：使用二分法分别找到 左邊界 left 和 右邊界 right ，易得數字 target 的數量為 right - left - 1；

class Solution {
    public int search(int[] nums, int target) {
        // 查找右邊界
        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;

        // 查找左邊界
        i = 0; j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] >= target) j = m - 1;
            else i = m + 1;
        }
        int left = j;
        return right - left - 1;
    }
}
           

1. 由于數組 nums中元素都為整數，是以可以分别二分查找 target和 target - 1 的右邊界，将兩結果相減并傳回即可;

2.2 代碼

class Solution {
    public int search(int[] nums, int target) {
        return search_right(nums, target) - search_right(nums, target - 1);
    }
    int search_right(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
           

3 複雜性分析

• 時間複雜度 O(log N) ： 二分法為對數級别複雜度；
• 空間複雜度 O(1) ： 幾個變量使用常數大小的額外空間；

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof