题目描述
统计一个数字在排序数组中出现的次数。
例如输入排序数组 [1,2,3,3,3,3,4,5] 和数字 3,由于 3 在这个数组中出现了 4 次,因此输出 4。
样例
输入:[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出:4
算法2
(二分查找) $O(logn)$
二分查找: 先找左端点 , 再找右端点
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
if(nums.empty()) return 0;
//找左端点
int l=0, r=nums.size()-1;
while(l < r){
int mid = (l + r) >> 1;
if(nums[mid] < k) l = mid + 1; //中点不属于答案部分,答案在右半部分
else r = mid;
}
if(nums[l] != k) return 0; //特判,l 或 r 都一样,因为l=r ,
int left = l; //记录左端点
//再找右端点
l = 0, r = nums.size()-1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] <= k) l = mid ;
else r = mid - 1;
}
return r - left + 1;
}
};