思想：可以采用暴力求解的方法，但时间复杂度高
采用二分求解的方法，时间复杂度为O(logn)
具体操作如下：
寻找第一个K:当二分查找当前的元素为K，判断k是否是第一个k
如果当前元素的值不是k ,根据大于k或者小于K来判断k属于前半部分还是后半部分
寻找最后一个k，使用二分查找的方法，判断当前元素值是否是k,如果是k,并且后面没有k的元素值，如果后面有的话，low=midindex+1
如果当前的元素值不是k，判断大于k还是小于k的值，判断二分查找前半部分还是后半部分
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int len=data.size();
if(len==0 || data.empty())
return 0;
int number=0;
int left=Getfirstk(data,0,len-1,len,k);
int right=Getlastk(data,0,len-1,len,k);
if(left>-1 && right>-1)
number= right-left+1;
return number;
}
int Getfirstk(vector<int>&data,int low,int high,int n,int k)
{
if(low>high)return -1;
int midindex=(low+high)>>1;
int middata=data[midindex];
//当data[midindex]==k,分成两种情况
if(middata==k)
{
//当前元素是第一个k
if((midindex>0 && data[midindex-1]!=k )|| midindex==0)
{
return midindex;
}
//当前元素的值不是第一个K
else
{
high=midindex-1;
}
}
else
if(middata>k)
{
high=midindex-1;
}
else
low=midindex+1;
return Getfirstk(data,low,high,n,k);
}
int Getlastk(vector<int>&data,int low,int high,int n,int k)
{
if(low>high)return -1;
int midindex=(low+high)>>1;
int middata=data[midindex];
if(k==middata)
{
if((midindex==n-1)||(midindex<n-1 && data[midindex+1]!=k))
{
return midindex;
}
else
low=midindex+1;
}
else
if(middata>k)
{
high=midindex-1;
}
else
low=midindex+1;
return Getlastk(data,low,high,n,k);
}
};