349. Sorted Occurrences
A librarian keeps a sorted list of catalogue numbers, and the same number may appear on several copies of a book. She asks how many copies of a given catalogue number, target, are on the shelf.
Given the sorted array nums (non-decreasing, repeats allowed) and an integer target, return how many times target appears in nums. Counting one by one is O(n); your solution should take O(log n) time. If the number is not present, return 0.
Example 1
- Input:
- nums = [1,3,3,3,8], target = 3
- Output:
- 3
- Explanation:
The number 3 appears three times.
Example 2
- Input:
- nums = [1,3,3,3,8], target = 4
- Output:
- 0
- Explanation:
4 is not in the array, so the answer is 0.
Constraints
0 ≤ nums.length ≤ 106
-109 ≤ nums[i], target ≤ 109nums is sorted in non-decreasing order.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)