题目描述

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

示例 1:

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

示例 2:

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

提示：

• $0 <= nums.length <= 10^{5}$
• $-10^{9} <= nums[i] <= 10^{9}$
• $nums$ 是一个非递减数组
• $-10^{9} <= target <= 10^{9}$

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

---

算法

(二分) $O(logn)$

在排序数组中快速找一个数可以用二分，题目要求找出连续的一段数 $target$ 的个数，可以做两次二分，二分左端点和二分右端点。

算法步骤：

1. 二分左端点的条件：找到第一个大于等于 $target$ 的数的位置 $left$
2. 二分结束，如果左端点对应的值不是 $target$，说明 $target$ 不存在，直接返回 $0$，否则继续二分右端点
3. 二分右端点的条件：找到最后一个个小于等于 $target$ 的数的位置 $right$

最后返回出现的次数 $right - left + 1$。

时间复杂度

二分的时间复杂度为 $O(logn)$

空间复杂度

$O(1)$

C++ 代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return 0;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if (nums[l] != target) return 0;

        int left = l;
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1ll >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }

        return r - left + 1;
    }
};