AcWing 67. 数字在排序数组中出现的次数
原题链接
简单
作者:
well188
,
2020-09-25 10:04:31
,
所有人可见
,
阅读 373
暴力二分法
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<n;i++){
int l=0,r=n-1;
while(l<r){
int mid=l+r>>1;
if(nums[mid]>=i) r=mid;
else l=mid+1;
}
if(nums[l]!=i) return i;
}
}
};
最优二分法
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
int l=0,r=nums.size();
while(l<r){
int mid=l+r>>1;
if(nums[mid]!=mid) r=mid;
else l=mid+1;
}
return l;
}
};
强烈推荐把二分模板的范围改为左闭右开的结构。这样更自然,能够秘密处理很多特判,本题就是很好的证明。