题目:
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:
[5, 3]
is also correct.分析:
两个相等的数异或结果为0。因此,首次扫描数组,得到两个单独的数a、b的异或结果axorb。因为a和b不相等,因此axorb一定不为0,且二进制位为1的位a和b一定不同。任取axorb中的一个不为0的二进制位,可以将原数组元素分成两组异或即得结果。
注:n & (-n)为n从低位向高位,第一个非0位所对应的数字
参考代码:
class Solution
{
public:
vector<int> singleNumber(vector<int>& nums)
{
size_t length = nums.size();
vector<int> results;
results.reserve(2);
if (0 == length) return results;
int axorb = 0;
for (size_t i = 0; i < length; i++)
axorb ^= nums[i];
int mask = axorb & (-axorb); // 取得axorb从低位向高位,第一个非0位所对应的数字
int a = 0;
int b = 0;
// axorb二进制位为1的位a和b一定不同,利用这个不为1的位将原数组元素分成两组异或即得结果
for (size_t i = 0; i < length; i++)
{
if (mask & nums[i]) a ^= nums[i];
else b ^= nums[i];
}
results.push_back(a);
results.push_back(b);
return results;
}
};