【剑指Offer】37、数字在排序数组中出现的次数
2024-09-01 21:11:52
题目描述:
统计一个数字在排序数组中出现的次数。例如,输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于数字3在该数组中出现了4次,所以函数返回4。
解题思路:
既然输入的数组是有序的,所以我们就能很自然的想到用二分查找算法。以题目中给的数组为例,一个比较自然的想法是用二分查找先找到一个3,由于要计算的是输出的次数,所以需要在找到的这个3的左右两边分别再进行顺序扫描,进而得到3的个数,这样最坏的情况下时间复杂度仍然是O(n),和直接顺序扫描的效率相同。
因此,需要考虑怎样更好的利用二分查找算法,由于数组有序,如果知道了第一个k出现的位置和最后一个k出现的位置,那么我们就可以直接算出有多少个k。因此将思路转化为通过二分查找求第一个和最后一个k出现的位置。
以第一个k出现的位置为例,利用二分查找算法可以直接对数组进行二分,而每次总是拿中间的数字和k做比较,如果中间的数字大于k,那么第一个k只有可能出现在左边,下一次直接在数组左半段继续进行二分查找;如果中间的数字小于k,则第一个k只有可能出现在右边,则在右半段再查找;如果中间的数字等于k,我们先判断它前面的一个数字是不是k,如果不是,那么这个中间的数字就是第一个出现的位置,反之,如果中间数字前面的数字是k,那么第一个k仍然在前半段,继续查找。
同理,找最后一个k出现的位置方法类似,可以使用两个函数分别获得。
编程实现(Java):
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int first=getFirstIndex(array,k);
int last=getlastIndex(array,k);
if(first==-1 || last==-1)
return 0;
return last-first+1;
}
//二分查找
public int getFirstIndex(int[] array,int k){
int res=-1;
if(array==null||array.length==0)
return res;
int low=0,high=array.length-1;
while(low<=high){ //要有=
int mid=low+(high-low)/2;
if(array[mid]<k)
low=mid+1;
else if(array[mid]>k)
high=mid-1;
else { //相等
mid=mid-1;
if(mid<low || array[mid]!=k)
return mid+1;
else
high=mid;
}
}
return res;
}
public int getlastIndex(int[] array,int k){
int res=-1;
if(array==null||array.length==0)
return res;
int low=0,high=array.length-1;
while(low<=high){ //要有=
int mid=low+(high-low)/2;
if(array[mid]<k)
low=mid+1;
else if(array[mid]>k)
high=mid-1;
else { //相等
mid=mid+1;
if(mid>high || array[mid]!=k)
return mid-1;
else
low=mid;
}
}
return res;
}
}
最新文章
- C++ 为什么拷贝构造函数参数必须为引用?赋值构造函数参数也必须为引用吗?
- Gym 101102D---Rectangles(单调栈)
- Notification
- get请求乱码
- Windows Server 2008 HPC 版本介绍以及的Pack
- 01day2
- 注册UBER(优步)司机常见问题,如何注册uber(优步)司机
- Docker 安装命令
- Linux通过使用Sambaserver示例
- ajax 跨域携带COOKIE
- Kruskal算法的实现
- thinkphp3.2后台模块怎么添加(admin),直接复制Home?还是在入口文件生成?
- 指针数组与带参main函数
- SQL Server 远程更新目标表数据
- 通过sort()方法实现升序和降序排列
- ajax提交 返回中文乱码问题
- mysql之limit m,n
- vs调试程序时发现变量、类等程序找不到混乱问题
- Codeforces 483B - Friends and Presents(二分+容斥)
- Spring Security构建Rest服务-0102-Spring Social开发第三方登录之qq登录