面试题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/

Solutions

1. binary search

class Solution {
public:
    int bisearch(vector<int> & nums, int target) {
        if (!nums.size() || target > nums.back())
            return nums.size();
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (target > nums[mid])
                lo = mid + 1;
            else
                hi = mid;
        }

        return lo;
    }
    int search(vector<int>& nums, int target) {
        int lo = bisearch(nums, target);
        if (lo == nums.size() || nums[lo] != target)
            return 0;
        int up = bisearch(nums, target + 1);
            return up - lo;
    }
};

Or

class Solution {
public:
    int search(vector<int>& nums, int target) {
        auto lo = lower_bound(nums.begin(), nums.end(), target);
        if (lo == nums.end() || *lo != target)
            return 0;
        auto up = lower_bound(nums.begin(), nums.end(), target + 1);

        return up - lo;
    }
};