二分
这题的其中一个边界条件真是让我大开眼界…不知是我读题
有问题还是他表述不清
看了y总的方法后深感惭愧,自己二分的思路还是不够清楚,加了很多
冗余的边界判断,虽然也ac了;评论区有个大佬的代码甚至不需要任何的
特殊判断,膜拜。
自己的写法
public:
int missingNumber(vector<int>& nums) {
int len = nums.size();
if(len == 0)return 0;
int l = 0, r = len - 1;
while(l < r && nums[r] > r){
int mid = (l + r) / 2;
if(nums[mid] > mid)
r = mid;
else
l = mid + 1;
}
if(!l && !nums[0])//若缺失的数字在序列尾如[0,1,2]
return len;
if(!r && nums[0])//若缺失的数字在序列头如[1,2,3]
return 0;
return l;//缺失的数字既不在首也不在尾
}
};
y总做法
class Solution {
public:
int missingNumber(vector<int>& nums) {
int len = nums.size();
if(len == 0)return 0;
int l = 0, r = len - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] != mid)
r = mid;
else
l = mid + 1;
}
if(nums[r] == r) r ++ ;
return r;
}
};
最简洁的方法
class Solution {
public:
int missingNumber(vector<int>& nums) {
int i = 0, j = nums.size();
while (i < j)
{
int mid = i + j >> 1;
if (nums[mid] > mid) j = mid;
else i = mid + 1;
}
return i;
}
};