# 260. Single Number III 只出现一次的数字 III

@TOC

## # 题目描述

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?

## # 解题方法

### # 异或

``````class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
xor = 0
num1, num2 = 0, 0
for num in nums:
xor ^= num
while xor & mask == 0:
for num in nums:
if num & mask == 0:
num1 ^= num
else:
num2 ^= num
return [num1, num2]
``````

C++代码如下：

``````class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int res = 0;
for (int n : nums) res ^= n;
int a = 0, b = 0;
int mask = 1;
while ((mask & res) == 0) mask <<= 1;
for (int n : nums) {
if (n & mask)
a ^= n;
else
b ^= n;
}
return {a, b};
}
};
``````

### # 字典

``````class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
count = collections.Counter(nums)
res = []
for num, c in count.items():
if c == 1:
res.append(num)
return res
``````

C++代码如下：

``````class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
map<int, int> count;
for (int n : nums) count[n] ++;
vector<int> res;
for (auto p : count)
if (p.second == 1)
res.push_back(p.first);
return res;
}
};
``````

## # 日期

2018 年 3 月 3 日 2018 年 11 月 24 日 —— 周六快乐 2018 年 12 月 10 日 —— 又是周一！