LeetCode刷题（81）～数组中数字出现的次数【分组异或】

题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

  

 

  
1
  
2
 

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
 

  

 

  
1
  
2
  
3
 

限制：

• 2 <= nums.length <= 10000

解答 By 海轰

提交代码（哈希）

 vector<int> singleNumbers(vector<int>& nums) { unordered_map<int,int> m; for(int num:nums) ++m[num]; vector<int> res; for(unordered_map<int,int>::iterator it=m.begin();it!=m.end();++it) { if(it->second==1) res.push_back(it->first); } return res; }

  

 

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

运行结果

解答

Demo（分组异或：思路）

vector<int> singleNumbers(vector<int>& nums) { int sum=0; for(int num:nums) sum^=num; int temp=sum&(-sum);// 取sum最后边的1 int a=0; int b=0; for(int num:nums) { if(temp&num) a^=num; else b^=num; } return {a,b}; }

  

 

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

运行结果

算法

1. 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
2. 在异或结果中找到任意为 1 的位。
3. 根据这一位对所有的数字进行分组。
4. 在每个组内进行异或操作，得到两个数字

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

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

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