题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

 

思路：由于性质：a ^ a = 0 ; 0 ^ n = n; 由于数组中有两个数字只出现一次，所以：

1.  将数组中的所有数字 ^，得到的数是这两个数的  ^，

2.  找到两个数 ^ 结果的最后一个1，即为两个数不相同的位

3.根据该位分组，则每一组中只有一个只出现一次的数字。

4.将两个组，分别 ^ ,则分别得到要求的两个数。

代码：

void FindNumsAppearOnce(vector
     
       data,int* num1,int *num2) {        int len = data.size();        int num = 0;        for(int i = 0; i < len;i++)        {            num = num^data[i];        }        int tmp = 1;        while((num&tmp) == 0)        {            tmp = tmp<<1;        }        int arr1[500],arr2[500];        int id1 =0 ;        int id2 = 0;        for(int i = 0; i < len;i++)        {            if((data[i] & tmp) == 0)                (*num1)^=data[i];            else                (*num2)^=data[i];        }    }