在给定的一个已经排好序的数组中,找出指定数字出现的次数;例如数组[1,2,3,3,3,4,5]中3出现的次数为3次。
时间: 2024-05-15 08:14:08 浏览: 9
可以用二分查找的思想来解决这个问题。先使用二分查找找到指定数字第一次出现的位置,再找到指定数字最后一次出现的位置,两者相减即可得到指定数字出现的次数。
以下是一个 Python 实现:
```python
def binary_search(nums, target, find_first):
"""
二分查找函数
:param nums: 已经排好序的数组
:param target: 目标数字
:param find_first: 是否查找第一次出现的位置
:return: 目标数字第一次或最后一次出现的位置
"""
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target or (find_first and nums[mid] == target):
right = mid - 1
else:
left = mid + 1
return left if find_first else right
def count_occurrences(nums, target):
"""
计算指定数字在数组中出现的次数
:param nums: 已经排好序的数组
:param target: 目标数字
:return: 指定数字在数组中出现的次数
"""
first = binary_search(nums, target, True)
if first == len(nums) or nums[first] != target:
return 0
last = binary_search(nums, target, False)
return last - first + 1
```
测试代码:
```python
nums = [1, 2, 3, 3, 3, 4, 5]
target = 3
print(count_occurrences(nums, target)) # 输出 3
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)