题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路：
因为有2个数字只出现了一次，而其他的数字都是2次，可以通过异或运算，得到最后这2个只出现一次的数字的 异或结果值。这种值必然不为0。
然后找出这个数字二进制中，最低位为1的位数，必然那一位一个是0，一个是1。
通过这个条件将原数组分为2部分，分别异或，得到结果。
代码：
class Solution {
public:
void FindNumsAppearOnce(vector<int> data, int* num1, int *num2)
{
int res = , tag = ;
if (data.empty())
{
num1 = num2 = ;
}
for (int i = ; i < data.size(); i++)
{
res ^= data[i];
}
for (; tag < ; tag++)
{
if ((res & (<<tag)) != )
break;
}
for (int i = ; i < data.size(); i++)
{
if ((data[i] & ( << tag)) == )
*num1 ^= data[i];
else
*num2 ^= data[i];
}
}
};
题2：
一个数组中有一个数字只出现一次。
思路：
直接遍历异或整个数组，得到的就是只出现一次的那个数字。
题3：
一个数组中，一个数字出现1次，其他都出现3 次
思路：
开辟一个位数的数组，遍历远数组记录所有元素的2进制，位数和。
遍历位数数组，将值除3取余，最后一个位数数组上留下来的就是最后这个只出现一次的数组。
代码：
public static int find1From3(int[] a){
int[] bits = new int[32];
int len = a.length;
for(int i = 0; i < len; i++){
for(int j = 0; j < 32; j++){
bits[j] = bits[j] + ( (a[i]>>>j) & 1);
}
}
int res = 0;
for(int i = 0; i < 32; i++){
if(bits[i] % 3 !=0){
res = res | (1 << i);