二分查找-268.丢失的数字-力扣(LeetCode)
一、题目解析
1.数据是无序的
2.数据是独一无二的
二、 算法解析
解法1：哈希表 空间复杂度O(N)
将数组元素插入到hash表中，如果hash[i] == 0，则缺失元素为i
解法2：位运算(^)
由于异或运算的性质：a^a=0，0^a=a，(a^b)^c=(a^c)^b。结合性质异或结果就是缺失的数
解法3：高斯求和公式
由于[0，n]有n+1个数，在数组中[0，n-1]有n个数，通过高斯求和公式求出n+1个元素的总和，减去数组中的n个数，剩下的就是缺失的数
解法4：排序+二分查找
由于数据是无序的，所以先用sort函数进行排序
虽然这里重点是二分查找，但还是建议把4种解法都尝试一遍
三、代码示例
解法1：
int hash[10004];int missingNumber(vector<int>& nums)//解法1：哈希表 空间复杂度为O(N){int ret = 0;for(auto& e : nums) hash[e] = 1;for(int i = 0;i<nums.size()+1;i++){if(!hash[i]){ret = i;break;}}return ret;}
解法2：
int missingNumber(vector<int>& nums)//解法2：位运算{int ret = 0;for(auto e : nums) ret ^= e;for(int i = 1;i<nums.size()+1;i++){ret ^= i;}return ret;}
解法3：
int missingNumber(vector<int>& nums)//解法3：高斯求和{int sum = 0;sum = (nums.size()*(nums.size()+1))/2;for(auto e : nums) sum -= e;return sum;}
解法4：
int missingNumber(vector<int>& nums)//解法4：二分查找{sort(nums.begin(),nums.end());int left = 0,right = nums.size()-1;while(left<right){int mid = left + (right - left)/2;if(nums[mid] == mid) left = mid + 1;else right = mid;}return nums[right] == right ? right+1 : right;}