数组中只出现一次的数字

问题描述

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

思路

1. 这个问题的初级版本：一个整型数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。解决初级版本最优的思路是使用异或运算符。将数组中所有元素做异或运算，最后得到的数就是那一唯一的只出现一次的数字。

2. 以上思路基于异或运算的几个性质：(1) a ⊕ a = 0 ;(2) a ⊕ b = b ⊕ a (3) a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;(4) d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c;(5) a ⊕ b ⊕ a = b;(7)a⊕0=a。异或运算的规则简单说就是相同为0不同为1

3. 对于本题，有两个只出现了一次的数字。很容易想到的解法是利用HashSet,遍历数组如果HashSet中不存在当前元素，则将当前元素加入HashSet，如果存在就从HashSet移除当前元素，最后剩下的两个元素就是我们要找的两个数字。

4. 有没有空间复杂度为O(1)的解法呢？思考初级版本，如果我们将数组分为两部分，每个数字分到其中一个部分再做初级版本中的异或运算，不就可以了吗。看来问题的关键是如果将数组分为两个各包含一个只出现一次的数字的数组：遍历数组中的每一个元素做异或运算，根据运算性质(1)和(3)我们可以推出，运算结果等于目标两个数的异或，假设为 a ⊕ b。由于a和b肯定是不一样的，所以a和b的二进制表示肯定至少有一位是不同的，xx1xxx和xxx0xxx。如果我们可以构造出一个00001000的数字，1出现在a,b不同的那一位上，然后用00001000分别和数组中的每一个数字做与运算，就能将元素分为两部分，一部分和00001000做与运算的值为0，一部分和00001000做与运算的值为1，其中a和b在不同的数组里。降维打击。

5. 如何构造出类似于00001000只有一个1其他全是0且1出现在a,b不同的某一位上的数呢？联想剑指offer的另外一道题目：“计算数字中1的个数”,利用a&(a-1)可以消除a最低位上的1。连续对a做a&(a-1)运算，当a=0前的最后一次运算，a就是0010000的形式了。

代码

 public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array==null)
            return;
        int diff=0;
        for(int num:array){
            diff^=num;
        }

        diff=helper(diff);

        for(int num:array){
            if((num&diff)==0){
                num1[0]=num1[0]^num;
            }else{
                num2[0]=num2[0]^num;
            }
        }
    }

    private int helper(int res){
        int temp=res;
        while(res!=0){
            temp=res;
            res=res&(res-1);
        }

        return temp;
    }