剑指offer56：数组中只出现一次的数字

题目描述

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

 思路：对于这个题目是没有较好的思路的，只能想到遍历然后利用map计数的方法。

看了书上的解释才学到了利用异或的方法进行计算

Tips: 1. 两个相同的数异或值为0

　　 2. 如果数组中除一个数字外，其余数字都出现两次，那么所有数字的异或值结果即为只出现一次的数

　  3. 题目中是存在两个只出现一次的数，那么所有数字的异或值就是这两个数字的异或值。

　　 4. 由于两个只出现一次的数的异或值肯定不为0，那么异或值的二进制的某一位一定为1，假设为第count位

　　 5. 接着把原数组分成两组，分组标准是第3位是否为1，那么两个只出现一次的数一定被分到两个不同的组

　　 6. 对两个组分别求异或值，即可求得两个只出现一次的数字

代码实现：

C++较繁琐的实现，注意这里int* num1,int* num2是指针传递，赋值的时候应*num1 = yihuo;

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int* num2) {
        int len = data.size();
        if(len == 0) return;
        //求数组所有数的异或值
        int result = data[0];
        for(int i=1;i<len;i++){
            result = result ^ data[i];
       }
        int count = 0;
        int temp = result;
        //求异或值第几位为1
        while(true){
            if(temp & 1 == 1)
                break;
            temp = temp >> 1;
            count++;
        }
        //把数组分为两部分
        vector<int> newData;
        for(int i=0;i<len;i++){
            if((data[i]>>count) & 1 == 1)
                newData.push_back(data[i]);
        }
        int yihuo = newData[0];
        for(int i=1;i<newData.size();i++){
            yihuo = yihuo ^ newData[i];
        }
        *num1 = yihuo;
        *num2 = (result ^ yihuo);
    }
};

 精简后的代码（java）：

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array.length == 0) return;
        //求所有结果的异或值
        int res = 0;
        for(int elem:array){
            res ^= elem;
        }
        //求该异或值从右边数第一个1的位数
        int num = 1;
        int indexOne = 0;
        while((res & num) == 0){
            num  <<= 1;
            indexOne++;
        }
        num1[0] = 0;
        for(int elem:array){
            if(((elem >> indexOne)&1)==1)
                num1[0] ^= elem;
        }
        num2[0] = num1[0] ^ res;
    }
}