【名企面试题】数组中只出现一次的数字

版权所有，转载请注明出处，谢谢！
http://blog.csdn.net/walkinginthewind/article/details/8138766

题目一：

一个整型数组里除了1个数字只出现一次之外，其他的数字都出现了两次。请写出程序找出这个只出现1次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

这个很简单，通过异或就可以除掉相同的数字，到最后只剩下一个只出现一次的数字。

参考代码如下：

void FindNumsAppearOnce(int data[], int length, int *num1, int *num2,int *num3){if(data == NULL || length < 3)return;const int INT_BITS = sizeof(int)*8;int result1[INT_BITS], result2[INT_BITS], cnt1[INT_BITS];memset(result1,0,sizeof(result1));memset(result2,0,sizeof(result2));memset(cnt1,0,sizeof(INT_BITS));int i, k, orAll = 0;for(i = 0; i < length; i++){for(k = 0; k < INT_BITS; k++){if(data[i] & (1 << k)){result1[k] ^= data[i];cnt1[k]++;}elseresult2[k] ^= data[i];}orAll ^= data[i];}k = 0;while(k < INT_BITS){if(result1[k]  && result2[k]){if(cnt1[k] & 1)*num1 = result1[k]; else*num1 = result2[k]; break;}k++;}k++;while(k < INT_BITS){if(result1[k]  && result2[k]){if(cnt1[k] & 1)*num2 = result1[k]; else*num2 = result2[k]; break;}k++;}*num3 = orAll ^ (*num1) ^ (*num2);}