一个整型数组除了两个数之外，其他数都出现了两次，找出这两个数在O（n）时间内
思路：首先将这个数组中所有的元素进行异或操作，即得到了这两个数组的异或结果。由于这两个数不相同，故异或结果中必然有某一位为1。将原始数组分为此位为1和为0的两个子数组，就转化成了在两个数组中找其他出现两次，存在某个数只出现一次的问题。对所有元素进行异或操作就可以得到这个数。
#include <iostream>#include<bitset>using namespace std;int indexFirst1(int num){ int indexOf1=0; while((num&1)==0&&indexOf1<32) { indexOf1++; num=num>>1; } return indexOf1;}bool isBit1(int num,int indexOf1){ return ((num>>indexOf1)&1);}void findOnce(int *a,int n){ int num1,num2,num; num1=num2=num=0; for(int i=0;i<n;i++) { num^=a[i]; } for(int i=0;i<n;i++) { if(isBit1(a[i],indexFirst1(num))) num1^=a[i]; else num2^=a[i]; } cout<<num1<<endl; cout<<num2<<endl;}int main(){ int a[12]={1,1,2,3,3,4,4,5,5,6,7,7}; findOnce(a,12); return 0;
}
输出结果：
6
2
