【剑指offer】数组在排序数组中出现的次数
2020-12-13 15:15
标签：方法 不同 复杂度 组元 pad offer double add dex 统计一个数字在排序数组中出现的次数。 分析：数组有序，采用二分查找无疑 两种方法，时间复杂度差不多，都是利用二分查找，不过统计k出现的次数有所不同而已 方法1：二分查找k，找到任意一个k的下标index，index向两边扩展即可 方法2：二分查找k+0.5和k-0.5的插入位置index1和index2，因为数组元素都是整数，index1-index2就是k出现的次数 时间复杂度:O（log N） 方法1： 方法2： 【剑指offer】数组在排序数组中出现的次数 标签：方法 不同 复杂度 组元 pad offer double add dex 原文地址：https://www.cnblogs.com/yinbiao/p/11576729.html题目描述
int GetNumberOfK(vectorint> v ,int k)
{
if(v.size()==0)
return 0;
//查找任意一个k的位置index
int low=0;
int high=v.size()-1;
int index=-1;
while(lowhigh)
{
int mid=(low+high)/2;
if(v[mid]==k)
{
index=mid;
break;
}
else if(v[mid]>k)
{
high=mid-1;
}
else if(v[mid]k)
{
low=mid+1;
}
}
if(index==-1)
return 0;
//index向两边扩展
int c=0;
for(int i=index-1; i>=0; i--)
{
if(v[i]==k)
c++;
else
break;
}
int n=v.size();
for(int i=index+1; i
//查找k的插入位置
int f(vectorint> &v,double k)
{
int low=0;
int high=v.size()-1;
while(lowhigh)
{
int mid=(low+high)/2;
if(v[mid]>k)
{
high=mid-1;
}else if(v[mid]k)
{
low=mid+1;
}
}
return low;
}
int GetNumberOfK(vectorint> v ,int k)
{
if(v.size()==0)
return 0;
int x=f(v,k+0.5);
int y=f(v,k-0.5);
if(x==-1||y==-1)
return 0;
//k+0.5和k+0.5的插入位置相减就是k出现次数
return x-y;
}