LeetCode 260 Single Number III 数组中除了两个数外，其他的数都出现了两次，找出这两个只出现一次的数...

104 阅读 0 评论 69 点赞

我是靠谱客的博主闪闪猫咪，这篇文章主要介绍LeetCode 260 Single Number III 数组中除了两个数外，其他的数都出现了两次，找出这两个只出现一次的数...，现在分享给大家，希望可以做个参考。

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements
appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
1.The order of the result is not important. So in the above example, [5, 3] is also correct.
2.Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

方法一：

首先计算nums数组中所有数字的异或，记为xor
令lowbit = xor & -xor，lowbit的含义为xor从低位向高位，第一个非0位所对应的数字
例如假设xor = 6（二进制：0110），则-xor为（二进制：1010，-6的补码）
则lowbit = 2（二进制：0010）

复制代码

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
33
34
35
 1 class Solution {
 2 public:
 3
vector<int> singleNumber(vector<int>& nums) {
 4
int size=nums.size();
 5
if(size==0||nums.empty())
 6
return vector<int>();
 7
int diff=0;
 8
for(auto &ele:nums)
 9
diff^=ele;
10
vector<int> res(2,0);
11
diff&=-diff;//从低位向高位，第一个非0位所对应的数字
12
for(auto &ele:nums)
13
if(diff&ele)
14
res[0]^=ele;
15
else
16
res[1]^=ele;
17
return res;
18 
}
19 };

方法二：

复制代码

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
33
34
35
36
37
38
39
40
41
 1 class Solution {
 2 public:
 3
vector<int> singleNumber(vector<int>& nums) {
 4
int size=nums.size();
 5
if(size==0||nums.empty())
 6
return vector<int>();
 7
int sum=0;
 8
for(auto &ele:nums)
 9
sum^=ele;
10
vector<int> res(2,0);
11
//从低位向高位，第一个非0位所对应的数字
12
int n=1;
13
while((sum&n)==0)
14
n=n<<1;
15
for(auto &ele:nums)
16
if(n&ele)
17
res[0]^=ele;
18
else
19
res[1]^=ele;
20
return res;
21 
}
22 };