题目:面试题 17.04. 消失的数字 - 力扣（LeetCode）
思路
思路一:遍历数组nums，将数组中的元素加入到哈希集合中，然后依次从0到n检查是否在哈希集合中，如果不在则是我们要找的数字。
思路二:数组nums中有n个数，在这n个数的后面添加从0到n的每个整数，则添加了n+1个整数，共有2n+1个整数。在2n+1个整数中，消失的数字只在后面n+1个整数中出现一次，其余的数字在前面n个整数中和后面n+1个整数中各出现一次，即其余的数字都出现了两次。
根据出现的次数的奇偶性，可以使用按位异或运算得到消失的数字。按位异或运算满足交换律和结合律，且对任意整数x都满足x^x=0和x^0=x;
解题
class Solution { public: int missingNumber(vector<int>& nums) { //1.哈希表 unordered_set<int> set; int n=nums.size();//数组的大小 for(int i=0;i<n;i++) { //将数组放入哈希集合中 set.insert(nums[i]); } int miss=-1; for(int i=0;i<=n;i++) { //遍历查看有哪个数是哈希集合中没有的 if(!set.count(i)) { miss=i; break; } } return miss; } }; class Solution { public: int missingNumber(vector<int>& nums) { //2.异或 int x=0; for(int i=0;i<nums.size();i++) { x^=nums[i]; } for(int i=0;i<=nums.size();i++) { x^=i; } return x; } };
