题目：

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

 

思路1：

　　若一个整型数组中只有一个数字出现了一次，其他数字都出现了两次，则可以通过异或的方法得到该数字。而在该题目中，有两个数字只出现一次，若可以把这个数组分成2个子数组，两个数字分别位于2个子数组中，则可以通过上述方法得到这两个数字。

　　那如何得到2个子数组呢？

　　首先对该数组进行异或操作，最终得到的值为两个只出现一次的数字异或后的结果。由于这两个数字并不相同，因此异或后的结果并不为0。接下来，从最低位开始寻找为1的位。该位上的数字为1证明这两个数字在这一位上并不相同，因此可以以这一位的值对数组进行分类。该位为0的数字分为一组，为1的数字分为另外一组。这样就将两个只出现一次的数字分到了两个子数组中。最后，对这2个子数组进行异或操作，最终得到的结果为这两个数字的值。

 

代码1：

1 class Solution { 2 public: 3 void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { 4 if(data.size() < 2) 5 return; 6 7 int temp = 0; 8 9 for(int i = 0;i < (signed)data.size();i++) 10 temp ^= data[i]; 11 12 int index = findFirstBitIs(temp); 13 *num1 = *num2 = 0; 14 for(int i = 0;i < (signed)data.size();i++){ 15 if(IsBit(data[i],index)) 16 *num1 ^= data[i]; 17 else 18 *num2 ^= data[i]; 19 } 20 } 21 22 int findFirstBitIs(int num){ 23 int index = 0; 24 while(((num&1) == 0) && (index < 8*sizeof(int))){ 25 num = num >> 1; 26 index+=1; 27 } 28 return index; 29 } 30 31 bool IsBit(int num,int index){ 32 num = num >> index; 33 return (num&1); 34 } 35 }; View Code

 

思路2：

　　采用map存储数组中的数字。具体格式为<int,bool>，仅出现一次的数字的布尔值为false，出现2次的数字的布尔值为true。在将所有的数字都存入map后，遍历map，可以得到仅出现一次的2个数字。

 

代码2：

1 class Solution { 2 public: 3 void FindNumsAppearOnce(vector<int> data,int *num1,int *num2) { 4 map<int,bool> m; 5 map<int,bool>::iterator it; 6 int num = 1; 7 for(int i = 0;i < data.size();i++){ 8 it = m.find(data[i]); 9 if(it != m.end()) 10 m[data[i]] = true; 11 else 12 m[data[i]] = false; 13 } 14 for(it = m.begin();it != m.end();it++){ 15 if(it->second == false){ 16 if(num == 1){ 17 *num1 = it->first; 18 num++; 19 }else if(num == 2) 20 *num2 = it->first; 21 } 22 } 23 } 24 }; View Code

 

转载于:https://www.cnblogs.com/sindy/p/7400757.html