二分查找-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& 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& 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& nums)//解法3：高斯求和 { int sum = 0; sum = (nums.size()*(nums.size()+1))/2; for(auto e : nums) sum -= e; return sum; }
解法4：
int missingNumber(vector& 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; }
