面试100 34找出数组中唯一出现一次的两个数字
一问题描述
一个数组中，存在两个只出现一次的数字，其余的数字均出现两次。要求在时间复杂度o(n)，空间复杂度为o(1)的情况下找出这两个数字。
二 问题分析
此题实际考察了，对位操作的理解。首先进行简化，考虑只有一个数组中，只存在出现了一次的一个数字，其余数字在数组中出现两次，试
找出这个数字。
三 解决方案
首先 回忆 异或操作，任意数字与自身相异或，结果都为0.
还有一个重要的性质，即任何元素与0相异或，结果都为元素自身。
解决方案：
1 从数组的起始位置开始，对元素执行异或操作，则最后的结果，即为此只出现了一次的元素。
2 题目中，数组中存在两个不同的元素，若是能仿造上述的解决方案，将两个元素分别放置在两个数组中，然后分别对每个数组进行异或操作，
则所求异或结果即为所求。
3 首先对原数组进行全部元素的异或，得到一个必然不为0的结果，然后判断该结果的2进制数字中，为1的最低的一位。
然后根据此位是否为1 ，可以把原数组分为两组。则两个不同的元素，必然分别在这两个数组中。
4 然后对两个数组，进行异或操作，即可得到所求。
四 代码示例
#include <iostream>
using namespace std ;
const int N = 10 ;
int getSingle(int * a) //获取全部元素的异或结果
{
if(!a)
return -1;
int sum = a[0] ;
for(int i = 1; i < N; i++)
sum ^= a[i] ;
return sum ;
}
int getTwo(int * a ,int & one , int & two , int sum) //求数组中两个不同的元素
{
unsigned int flag = 1;
while(flag) //求异或结果，最低的为1的二进制位，根据此位是否为1，将元素分为两组，两个不同的元素，在此位必然，一个为1，一个为0
{
if(flag&sum)
break;
flag = flag << 1 ;
}
//下面将flag与每个元素相求与，根绝结果是否为1，将其化为两个数组
//分别计算每个数组的异或结果，并将结果，存储分别存储在one和two中。
one = two = 0 ;//0与任何数异或都为其自身，所以初始化的时候，应该初始化为0
for(int i = 0 ; i < N ;i++ )
{
if(a[i] & flag)
{
one ^= a[i] ;
}
else
{
two ^= a[i] ;
}
}
}
int main()
{
int a[N] = {3 , 5 ,8 , 8 , 5 , 3 ,1 ,4 ,4,10} ;
int single = getSingle(a) ;
int one = 0 ;
int two = 0;
getTwo(a ,one , two ,single) ;
cout<<single<<" "<<one<<" "<<two<<endl ;
system("pause") ;
return 0 ;
}