一个整形数组里除了两个数字外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字.
要求时间复杂度是On,空间复杂度为O1。
【题目思路】：
首先对于这道题我们会先想到：如果一个数组中，只有一个数字出现一次，那么我们很容易想到异或用法：
异或: X^X = 0，X^0 = X。
所以会将数组中所有的数异或起来，那么最后结果就是出现一次的数。
想到这我们思路豁然开朗：
将两个出现一次的数分别放在两个不同数组，然后对每个数组的所有数进行异或运算，那么结果就显然易见了。
伴随着想法的产生，那么复杂的问题又来了：怎样将两个出现一次的数分到不同数组？如何确保成对出现的数能分到一个数组？
这分组依据如何确定？
经过深思熟虑，我们知道，将所有数字异或一起，最后结果就是只出现一次的数字异或的结果，然后因为两个数不同，异或结果肯定不为0，那么至少存在一个1，此时我们找到第一个1所在位置，并标记起来，记为第n位，然后按照第n位是否为1，将数组分为两个子数组，由于分配中是按照第n位是否为1的标准分的，那么相同的数肯定会在同一数组。那么依次异或两个子数组，结果就出来了。
例子:
比如说1,1,2,2,3,4,5,5
最后异或的结果就是3^4=1110
根据倒数第4位上是否为1,将原先的数组分为2组:
第一组：1,1,2,2,3
第二组：4,5,5
这样分别异或,第一组得到3,第二组得到4，即达到目的。
【代码如下】：
//找出只出现一次的两个数
void NumbersAppearOnce(int data[],int length,int *num1,int *num2)
{
if(data==NULL||length<2)
return;
//将整个数组的每个元素进行异或
int ResultExcusiveOr=0;
for(int i=0;i<length;++i)
ResultExcusiveOr^=data[i];
//整个数组异或结果，最右边为1的位置
unsigned int indexof1=FindFirst1(ResultExcusiveOr);
*num1=*num2=0;
for(int j=0;j<length;++j)
{
if(IsBit1(data[j],indexof1))
*num1^=data[j];
else
*num2^=data[j];
}
}
//整数num最右边位1的位置即需要右移位数
unsigned int FindFirst1(int num)
{
int index=0;
while(((num&1)==0)&&(index<8*sizeof(int)))
{
num=num>>1;
++index;
}
return index;
}
//检验num的第index个位置是否为1
bool IsBit1(int num,unsigned int index)
{
num=num>>index;
return (num&1);
}
当然此类问题相关题目：
题目一为：给你1-1000个连续自然数，然后从中随机去掉两个，再打乱顺序，要求只遍历一次，求出被去掉的两个数。
（基本跟上面的题一样）；