面试题37：数组中只出现一次的数字
题目：整型数组中除了两个数字之外，其他的数字都出现两次，找出这两个只出现一次的数字
思路：利用异或运算的性质：任何一个数字异或自己都等于0；
1.从头到尾依次异或数组中的每个数字，最终得到的结果就是两个只出现一次的数字的异或结果；
2. 异或结果的二进制表示中至少有一位为1，找到结果数字中第一个为1的位的位置，记为第n位；
3. 以第n位是否为1为标准把原数组中的数字分为两个子数组，第一个子数组中的每个数字的第n位都为1，
第二个子数组中的每个数字的第n位都为0；
4. 最后分别对两个子数组进行异或运算，就可以求出两个只出现一次的数字
代码如下：
#include "stdafx.h"#include <iostream>using namespace std;//整型数组中除了两个数字之外，其他的数字都出现两次，找出这两个只出现一次的数字//要求：时间复杂度O(n)，空间复杂度：O(1)//判断在num的二进制表示中从右边数起的indexBit位是否为1bool IsBit1(int num, int indexBit){ num = num >> indexBit; return (num & 1);}//在num的二进制表示中找到最右边是1的位int FindFirstBitIs1(int num){ int indexBit = 0;while ((num & 1) == 0){num = num >> 1;indexBit++;}return indexBit;}void FindNumsAppearOnce(int nArr[], int nLength, int &num1, int &num2){ if (nArr == NULL || nLength < 2) { return; } int nResultExlusiveOR = 0;//记录数组中所有数进行异或之后的结果 for (int i=0; i<nLength; i++) { nResultExlusiveOR ^= nArr[i]; } int indexBit = FindFirstBitIs1(nResultExlusiveOR);//找到异或结果的二进制表示中最右边1的位置 //根据该位上为1或0将原数组分为两部分，然后对两部分数字分别进行异或运算，得到的两个数即为所求 for (int j=0; j<nLength; j++) { if (IsBit1(nArr[j], indexBit)) { num1 ^= nArr[j]; } else { num2 ^= nArr[j]; } }}int _tmain(int argc, _TCHAR* argv[]){int nArr[8] = {2,4,3,6,3,2,5,5};int nNum1 = 0;int nNum2 = 0;FindNumsAppearOnce(nArr, 8, nNum1, nNum2);cout << "只出现一次的数字为：" << nNum1 << " " << nNum2 << endl;system("pause");return 0;}运行结果：
