AcWing 68. 0到n-1中缺失的数字
原题链接
简单
作者:
牛奶小柒Luke
,
2021-02-12 15:47:45
,
所有人可见
,
阅读 195
二分
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if(nums.empty()) return 0;
int l = 0,r = nums.size() - 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;
}
};
哈希set
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
unordered_set<int> s;
for(int i = 0;i <= nums.size();++i){
s.insert(i);
}
for(auto x : nums){
s.erase(x);
}
return *s.begin();
}
};