剑指 offer 刷题（31）——数组中只出现一次的数字

一、题目

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

二、思路

利用异或运算。

异或运算的规则：参与异或的两个数，两个相应位相同则为 0，相异则为 1。

异或运算的特点：两个相同的数异或结果为 0，一个数和 0 异或的结果还是它本身。

把数组中的数都进行一次异或运算，结果就是两个只出现一次的数字异或的结果。由于这两个数字不同，异或的结果不为 0，并且结果中 1 所在的位表示两个数字的不同的位。所以，我们可以选定一个 1 所在的位（假设第二位是 1），将原数组分为两组：第二位为 1 的数为一组，其它的为另一组，这样这两个不同的数就分别位于两个组里。再对两个组分别进行异或运算，就找到了两个只出现了一次的数。

三、代码

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array.length == 2){
            num1[0] = array[0];
            num2[0] = array[1];
            return;
        }
        // 1.求出异或的结果
        int xor = 0;
        for(int i = 0; i < array.length; i++){
            xor = xor ^ array[i];
        }
        // 2.找到异或结果中任意一个 1 所在的位(这里找右边第一个 1)
        int index = 0;
        while((xor & 1) == 0 && index < 32){
            xor = xor >> 1;
            index++;
        }
        // 3.把数组分组后再异或(可以不断更新异或的结果，不用再创建额外的数组)
        for(int i = 0; i < array.length; i++){
            if(isBitOne(array[i], index))
                num1[0] ^= array[i];
            else
                num2[0] ^= array[i];
        }
    }
    
    // 判断一个数从右数的第 index 位是不是 1
    public boolean isBitOne(int num, int index){
        return ((num >> index) & 1) == 1;
    }
}