起源
受LeetCode系列题目启发
已提交贡献（然而几个月了都是Pending，发到博客来吧~
题目
给定一个正整数数组 nums，其中恰好有三个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那三个元素。
示例 :
输入: [1, 6, 2, 4, 1, 3, 2, 5, 6]
输出: [3, 4, 5]
注意：
- 结果输出的顺序并不重要，对于上面的例子，可以是 3, 4, 5 的任意排列。
- 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
解题
这道题比 “只出现一次的数字III” 多了一个只出现一个的数字，我们只要找到三个只出现一个的数字中一个，加入数组中，再使用 “只出现一次的数字III” 寻找两个只出现一次的数字即可
首先记 LSB(x) = x & (-x)，表示取x的二进制最低的位1，其他位均置为0，如LSB(100110b) = 000010b，若x > 0，则 LSB(x) > 0
设三个只出现一次的正整数为 a, b, c, 设 n = a ^ b ^ c（对数组中所有数进行异或可得n），由异或的交换律和结合律有 (n ^ a) ^ (n ^ b) ^ (n ^ c) = 0
显然也有 LSB(n ^ a) ^ LSB(n ^ b) ^ LSB(n ^ c) != 0， 即至少有一个二进制位是1，因为任意两个LSB(·)异或运算结果为0或者有两个二进制位1
设 k为LSB(LSB(n ^ a) ^ LSB(n ^ b) ^ LSB(n ^ c)) 的位1所在位置，即k是 LSB(n ^ a)， LSB(n ^ b)， LSB(n ^ c)为三者中最小的最低位1的位置，则 (n ^ a)， (n ^ b)， (n ^ c)三者在第 k 位上只有3种可能，有3个1，2个1或1个1。
如果有3个1或者1个1，则第 k位异或结果为1，与 (n ^ a) ^ (n ^ b) ^ (n ^ c) = 0矛盾
因此(n ^ a)， (n ^ b)， (n ^ c)三者在第 k 位上只能有2个1，我们现在要寻找的三个数种的第一个数就是第 k 位上是0的那个数，不妨设为c
为此，我们初始化n = 0遍历数组，依次计算n ^= arr[i]，得到n = a ^ b ^ c，
初始化lsb = 0，再次遍历数组，依次计算lsb ^= LSB(n ^ arr[i])，结果得到的 lsb 就是LSB(n ^ c) ，因为对于那些出现两次的数x，LSB(n ^ x) ^ LSB(n ^ x) = 0，而对于n ^ a和n ^ b，它们在第k位（也是它们的最低位的1）都是1，因此，LSB(n ^ a) ^ LSB(n ^ b) = 0
初始化c = 0，再次遍历数组，如果LSB(n ^ arr[i]) == lsb，计算c ^= arr[i]，最后结果c就是我们要寻找的数，因为LSB(n ^ arr[i]) == lsb筛选出的arr[i]最低位1的位置和lsb相同（也就是和c相同），这些数的异或结果只会留下c，出现两次的数都抵消了
C++代码
#include <iostream>
#include <vector>
using namespace std;
int LSB(int num){ //取最低位的1，其他位均置为0
return num & (-num);
}
vector<int> Two(vector<int> arr){ //寻找数组中两个只出现一次的数（其他数都出现两次）
int a_xor_b = 0, a = 0, b = 0, lsb = 0;
for (int i = 0; i < arr.size(); i++)
a_xor_b ^= arr[i];
lsb = LSB(a_xor_b);
for (int i = 0; i < arr.size(); i++)
if(arr[i] & lsb)
a ^= arr[i];
b = a_xor_b ^ a;
return vector<int>{a, b};
}
int OneOfThree(vector<int> arr){ //寻找数组中三个只出现一次的数中的一个（其他数都出现两次）
int a_xor_b_xor_c = 0, c = 0, lsb = 0;
for (int i = 0; i < arr.size(); i++)
a_xor_b_xor_c ^= arr[i];
for (int i = 0; i < arr.size(); i++)
lsb ^= LSB(a_xor_b_xor_c ^ arr[i]);
lsb = LSB(lsb);
for (int i = 0; i < arr.size(); i++)
if (LSB(a_xor_b_xor_c ^ arr[i]) == lsb)
c ^= arr[i];
return c;
}
vector<int> Three(vector<int> arr){ //寻找数组中三个只出现一次的数（其他数都出现两次）
int c = OneOfThree(arr);
arr.push_back(c);
vector<int> res = Two(arr);
res.push_back(c);
return res;
}
int main(){
vector<int> arr = {1, 6, 2, 4, 1, 3, 2, 5, 6};
vector<int> res = Three(arr);
for(int i = 0; i < 3; i++)
cout << res[i] << " ";
return 0;
}
参考
http://lijinma.com/blog/2014/05/29/amazing-xor/
http://www.360doc.com/content/14/0728/12/14505022_397625773.shtml