【剑指offer】40. 数组中只出现一次的数字

题目描述

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

思路

异或异或，顾名思义就是说相异为1，我们可以利用这点，把2个落单的数字按照他们不同的特征来分组。（这个特征当然就是不同的二进制位啦）分组之后问题就转化成纯异或来求的了。

leetcode上题目的题解，我自己写的。

方法一

class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int xor = array[0];
        for(int i = 1; i < array.length; i++) xor ^= array[i];
        int bit = getBit(xor);
        for(int num: array){
            if(((num>>>bit)&1)==1) num1[0] ^= num;
            else num2[0] ^= num;
        }
    }
    private int getBit(int xor){
        int res = 0;
        while((xor&1)!=1){
            res++;
            xor >>= 1;
        }
        return res;
    }
}