@TOC

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:

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

示例 2:

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

限制：

• 0 <= 数组长度 <= 50000

注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

解法一：暴力解法

直接遍历数组，当前元素和target相同 res++

时间复杂度：$O(n)$

Java代码

class Solution {
    public int search(int[] nums, int target) {
       if(nums == null || nums.length == 0) return 0;
       int res = 0;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == target){
                res++;
            }
        }
        return res;
    }
}

解法二：二分查找

题目中明显透露着排序，因此条件反射就是是否能二分。

找到小于等于target的最大索引位置right，大于等于target的最小索引位置left，则target出现次数就是right - left + 1；也就是我们找到的区间长度。

时间复杂度： $O(logn)$

二分模板可以看本人博客二分模板介绍

Java代码

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return 0;
        int l = 0,r = nums.length - 1,left = 0,right = 0;

        //找到小于等于target的最大索引位置
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1; 
        }
        right = l;

        //如果数组中并不存在target，直接返回0
        if(nums[right] != target) return 0;

        //找到大于等于target的最小索引位置
        l = 0;
        r = nums.length - 1;
        while(l <r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        left = l;

        return right - left + 1;
    }
}