题目描述
第一反应用遍历
但用二分法可以减少时间复杂度
C++ 代码
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
if(!nums.size()) return 0;
int l1=0, l2=0, r1=nums.size()-1, r2=nums.size()-1; //找到第一个为k的数
while(l1<r1){
int mid1 = l1+r1 >> 1;
if(nums[mid1]>=k) r1 = mid1;
else l1 = mid1 + 1;
}
while(l2<r2){ //找到最后一个为k的数
int mid2 = l2+r2+1 >> 1;
if(nums[mid2]<=k) l2 = mid2;
else r2 = mid2 - 1;
}
if(nums[l1]-k) return 0;
return l2-l1+1;
}
};