LeetCode刷题（172）～只出现一次的数字 III【分组异或】

题目描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

  

 

  
1
  
2
 

注意：

• 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
• 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

解答 By 海轰

提交代码（哈希）

vector<int> singleNumber(vector<int>& nums) { unordered_map<int,int> m; vector<int> ans; for(int num:nums) ++m[num]; for(auto i:m) { if(i.second==1) ans.push_back(i.first); } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

运行结果

提交代码（分组异或）

vector<int> singleNumber(vector<int>& nums) { int temp=0; for(int i:nums) temp^=i; temp= temp & -temp; int a=0; int b=0; for(int i:nums) { if(i& temp) a^=i; else b^=i; } return {a,b}; }

  

 

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

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-iii

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

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