剑指offer系列之三十九：数组中只出现一次的数字

题目描述

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

先考虑只有只有一个数字出现一次的情况，因为其他数字只出现了两次，所以对这两个数字进行异或运算的时候，其结果是0，那么那个只出现一次的数字进行异或运算的时候，其结果必然不是0，所以可以利用这点找出那个只出现一次的数字。现在考虑有两个数字出现一次的情况，仍然借鉴上面的思路，因为只出现一次的那个数字的异或结果不是0，遍历整个数组进行异或运算的结果也肯定不是0，现在可以对该数右边第一个是1的位的位置作为标准（记为n），将整个数组进行拆分，这样会得到两组数组，一组n位的位置的值都是1，两组则都是0。用一个简单的例子就可以说明这点：一个数组{1，2，2，3，3，4}，遍历进行异或运算的结果是0110，右边第一个不是0的位的位置的2，那么数组{1}和{2，2，3，3，4}。第一个数组的右数第2位的值都是0，而第二个数组右数第2位的值都是0。所以在对第一组进行异或运算的结果是1，第二个数组进行异或运算的结果是4，因为其他都出现了两次，异或运算之后变成了0。

根据上述思路，实现的代码如下（已被牛客AC）：

package com.rhwayfun.offer;

public class FindNumberAppearOnce {

    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        if(array == null || array.length < 2) return;
        int resultExclusiveOr = 0;
        for (int i = 0; i < array.length; i++) {
            resultExclusiveOr ^= array[i];
        }
        //找到右边第一个是1的位的位置
        int rightFirstIndexIs1 = findFirstIndexis1(resultExclusiveOr);
        //把该位是1的与不是1的数分别两部分
        for (int i = 0; i < array.length; i++) {
            if(isBit1(array[i],rightFirstIndexIs1)){
                num1[0] ^= array[i];
            }else{
                num2[0] ^= array[i];
            }
        }
    }

    //数num右数index为是否为1
    private boolean isBit1(int num, int index) {
        num = num >> index;
        return ((num & 1) == 1) ? true : false;
    }

    //找到右边第一个是1位的位置
    private int findFirstIndexis1(int resultExclusiveOr) {
        int index = 0;
        while(((resultExclusiveOr & 1) == 0) && index < 32){
            resultExclusiveOr = resultExclusiveOr >> 1;
            index++;
        }
        return index;
    }

    public static void main(String[] args) {
        int[] array = new int[]{2,4,3,6,3,2,5,5};
        int[] num1 = new int[]{0};
        int[] num2 = new int[]{0};
        new FindNumberAppearOnce().FindNumsAppearOnce(array, num1, num2);
        System.out.println(num1[0] + "," + num2[0]);
    }
}