优选算法_丢失的数字_位运算_C++

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