1 题目描述
统计一个数字在排序数组中出现的次数。
2 思路和方法
（1）查找有序数组，首先考虑使用二分查找，使时间复杂度为O（log n）。更改二分查找的条件，不断缩小区间，直到区间头和区间尾均为k时停止，计算得到区间长度。O（n*log(n)）。
（2）两行代码就搞定，就是用C++ stl里面的lower_bound和upper_bound，lower_bound是找出不小于即大于等于的第一个数的下标 ；upper_bound是找出大于的第一个数的下标。
3 C++核心代码
（1）
class Solution {
public: // 二分查找 O(log n)
int GetNumberOfK(vector<int> data ,int k) {
if (data.size() <=)
return ;
int count = ;
int begin = ;
int end = data.size()- ;
while (begin<=end){
int mid = (begin + end) /;
if (data[begin]==k && data[end] == k)
break;
// 缩小start和end的范围，使start指向第一个k，end指向最后一个k
if (data[begin] < k)
++begin;
if (data[end] > k)
--end;
if (data[mid]< k){
end = mid -;
} else if (data[mid] > k){
begin = mid +;
}
}
if (data[begin] ==k && data[end]==k)
return end - begin + ; // beg和end分别对应第一个和最后一个k所在位置
else
return ; // beg>end 不存在该元素
}
};（2）
class Solution
{
public:
int GetNumberOfK(vector<int> data ,int k)
{
int s1 = lower_bound(data.begin(),data.end(),k)-data.begin();
int s2 = upper_bound(data.begin(),data.end(),k)-data.begin();
//cout<<s1<<" "<<s2<<endl;
return s2-s1;
}
};
参考资料
https://blog.csdn.net/zjwreal/article/details/88774692