LeetCode刷题（125）～错误的集合【分组异或】

题目描述

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1:

输入: nums = [1,2,2,4]
输出: [2,3]

  

 

  
1
  
2
 

注意:

• 给定数组的长度范围是 [2, 10000]。
• 给定的数组是无序的。

解答 By 海轰

提交代码（哈希+异或）

vector<int> findErrorNums(vector<int>& nums) { vector<int> ans; unordered_map<int,int> m; for(int num:nums) { ++m[num]; if(m[num]==2) { ans.push_back(num); break; } } int temp=0; for(int i=0;i<nums.size();++i) { temp=temp^(i+1)^nums[i]; } ans.push_back(temp^ans[0]); return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

运行结果

提交代码(分组异或)

vector<int> findErrorNums(vector<int>& nums) { int sum=0; for(int i=0;i<nums.size();++i) { sum=sum^nums[i]^(i+1); } int mid=sum&(-sum); int temp1=0; int temp2=0; for(int i=1;i<=nums.size();++i) { if(mid&i) temp1^=i; else temp2^=i; } for(int num:nums) { if(mid&num) temp1^=num; else temp2^=num; } int count=0; for(int num:nums) { if(num==temp1) ++count; } if(count==2) return {temp1,temp2}; else return {temp2,temp1}; return {}; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
 

运行结果

提交代码（分组异或 优化）

vector<int> findErrorNums(vector<int>& nums) { int sum=0; for(int i=0;i<nums.size();++i) { sum=sum^nums[i]^(i+1); } int mid=sum&(-sum); int temp1=0; int temp2=0; for(int i=0;i<nums.size();++i) { if(mid&(i+1)) temp1^=(i+1); else temp2^=(i+1); if(mid&nums[i]) temp1^=nums[i]; else temp2^=nums[i]; } int count=0; for(int num:nums) { if(num==temp1) ++count; } if(count==2) return {temp1,temp2}; else return {temp2,temp1}; return {}; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-mismatch

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108416055