当前位置 博文首页 > 中流击水，浪遏飞舟：二分法&&剑指 Offer 53 - I. 在排
目标：在非递减数组中统计一个数字出现的次数。
class Solution {
public:
int search(vector<int>& nums, int target) {
//O(n)时间复杂度，直接遍历
int count=0;
for(auto x:nums){
if(x==target){
count++;
}
}
return count;
//或者直接一行代码:return count(nums.begin(),nums.end(),target);
}
};
参考了那个男人的题解：
面试题53 - I. 在排序数组中查找数字 I（二分法，清晰图解）
class Solution {
public:
int search(vector<int>& nums, int target) {
return binsearch(nums,target)-binsearch(nums,target-1);
}
int binsearch(vector<int> nums,int target){ //二分查找传入数组和查找的值
int left=0,right=nums.size()-1;
while(left<=right){
int mid=left+((right-left)>>1);
if(nums[mid]<=target){
left=mid+1;
}
else{
right=mid-1;
}
}
//cout<<left<<" "<<right<<" "<<endl;
return left;
}
};
