算法:数组中只出现一次的数字

数组中只出现一次的数字

数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

分析

对于一个数组中, 如果只有一个数字出现一次, 而其他所以数字出现两次, 则可以通过a[i] ^ a[i + 1]异或所有元素, 而由于x ^ x == 0, 所以可得这个元素;

对于数组中有两个元素只出现了一次, 分析可知当异或了整个数组元素之后, 结果即为x ^ y.(x, y即是两个出现了一次的元素)

可以通过添加一个mask: x与y某一位不同的而创建的数字. 通过mask可以把数组分为两个部分, 分组标准即为与mask异或是否为0.

如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

代码

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int xor = 0;
        for (int n : array) {
            xor ^= n;
        }
        // 在xor中找到第一个不同的位对数据进行分类
        // 分类为两个队列对数据进行异或求和找到我们想要的结果
        int mask = 1;
        while ((mask & xor) == 0) mask <<= 1;

        int res1 = 0, res2 = 0;
        for (int n : array) {
            if ((mask & n) == 0) res1 ^= n;
            else res2 ^= n;
        }
        num1[0] = res1;
        num2[0] = res2;
    }
}