优选算法_丢失的数字_位运算_C++
一.题目解析
算法1:哈希表
我们要找到一个没有的数字,先把nums存入hash表中,对比缺失的数字是哪个
代码实现
class Solution { public: int missingNumber(vector<int>& nums) { int n=nums.size(); unordered_map<int,int>hash(n); int count=0; for (int num : nums) //将数组存入哈希表 { hash[num] = true; } for(int i=0;i<=n;i++) { if(!hash.count(i))return i; } return -1; } };算法优化:在对比hash表的时候可以使用二分查找
算法优化:
class Solution { public: int missingNumber(vector<int>& nums) { int n=nums.size(); unordered_map<int,int> hash(n); for(int num:nums) { hash[num]=1; } int left=0,right=n; while(left<right) { int mid=left+(right-left)/2; if(hash.count(mid))left=mid+1; else right=mid; } return left; } };算法2:高斯求和
缺失的数字是在一个连续相邻的即0~n中,显然和减去数组和即是结果
代码实现:
class Solution { public: int missingNumber(vector<int>& nums) { int n=nums.size(); int sum=0; for(int i=0;i<n;i++) { sum+=nums[i]; } int sum1=(0+n)*(n+1)/2; int ret=sum1-sum; return ret; } };//高斯求和算法三:位运算
^(异或)的性质是"消消乐"即a^a=0,所以我们异或上一个连续的数组,相同的消除,留下的即是结果\
代码实现:
class Solution { public: int missingNumber(vector<int>& nums) { int ret=0; int n=nums.size(); for(int i=0;i<n;i++) { ret^=nums[i]; } for(int i=0;i<=n;i++) { ret^=i; } return ret; } };//位运算