Count How Many Times a Number Appears in a Sorted Array
Implement countOccurrences
Given an array
nums sorted in non-decreasing order and an integer target, return how many times target appears in nums.
Solve it in O(log n) time by finding the first and last positions of target with two binary searches, rather than scanning every element.
Example 1:
Input: nums = [1,3,5,5,5,7,9], target = 5
Output: 3
Example 2:
Input: nums = [1,3,5,5,5,7,9], target = 6
Output: 0
Example 3:
Input: nums = [1], target = 1
Output: 1
+ 4 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 10⁴ - ●
-10⁴ ≤ nums[i], target ≤ 10⁴ - ●
nums is sorted in non-decreasing order (duplicates are allowed)
nums =
[1, 3, 5, 5, 5, 7, 9]
target =
5