【答案解析】一个整型数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
如果本题对时间复杂度没有要求的话，最容易想到的方法就是首先对这个整型数组排序，然后从第一个数字开始遍历，比较相邻的两个数，从而找出这个只出现一次的数字，所以其时间复杂度最快为O(nlogn)。
由于时间复杂度与空间复杂度的限制，该种方法不可取，所以需要一种更高效的方式。题目强调只有一个数字出现一次，其他的出现了两次，首先想到的是异或运算的性质：任何一个数字异或它自己都等于0，根据这一特性，如果从头到尾依次异或数组中的每一个数字，因为那些出现两次的数字全部在异或中抵消掉了，所以最终的结果刚好是那个只出现一次的数字。
程序示例如下：
#include＜stdio.h＞
int findNotDouble(int a[],int n)
{
int result=a[0];
int i;
for(i=1;i＜n;++i)
result^=a[i];
return result;
}
int main()
{
int array[]={1,2,3,2,4,3,5,4,1};
int len=sizeof(array)/sizeof(array[0]);
int num=findNotDouble(array,len);
printf("%d/n",num);
return 0;
}
程序输出结果：
5
引申：如果题目改为整型数组中除了两个数字之外，其他的数字都出现了两次，如何求解这两个只出现一次的数?
在上述解决方案的基础上，如果能够把原数组分为两个子数组，在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次，问题就可以很容易地解决了：分别对两个子数组按照上述解决方案执行结果。
现在问题的难点就是如何划分为两个符合求解方案的子数组。首先从头到尾依次异或数组中的每一个数字，因为其他数字都出现了两次，在异或中全部抵消掉了，所以最终得到的结果将是两个只出现一次的数字的异或结果。而这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1，否则就为0了。在结果数字中找到第一个为1的位的位置，记为第N位，此时以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。通过这种方法就可以把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。
程序示例如下：
#include＜stdio.h＞
void fmdOnce(int data[],int n,int &num1,int &num2)
if(n＜5)
return;
int r1=0;
for(int i=0;i＜n;i++)
r1^=data[i];
int bitNum=0;
while(!(r1 & 0x1))
{
r1＞＞=1;
++bitNum;
}
int flag=(1＜＜bitNum);
num1=0;
num2=0;
for(int j=0;j＜n;j++)
{
if(data[j] & flag)
num1^=data[j];
else
num2^=data[j];
}
}
int main()
{
int array[]={1,2,3,2,4,3,5,1};
int num1, hum2;
findOnce(array,sizeof(array)/sizeof(array[0]),num1,num2);
printf("%d/n%d/n",num1,num2);
return 0;
}
程序输出结果：
5
4