【算法题】数组中只出现一次的两个数字

1. 题目

标签: 哈希表, 位运算.

2. 思路

2.1 哈希表

最简单的方法肯定是用哈希表, 遍历一遍数组找到只出现一次的两个数字. 相关代码就不贴了. 不过这样的话空间复杂度是 O(n), 太高了.

2.2 位运算

另一个想法就是位运算.
我们已知, 两个相同的数字做异或的结果为 0, 如 1001(十进制为9) ⊕ 1001 = 0, 而不同数字异或: 1001 ⊕ 0101 = 1100.
那么显然, 如果数组中存在一个只出现一次的数字, 可以把所有数组元素异或一下求出, 如: 1⊕1⊕3⊕6⊕6⊕5⊕5 = 3.
但问题是现在有两个只出现了一次的数字, 异或下来的结果为: 1⊕1⊕3⊕6⊕6⊕5⊕5⊕4 = 3⊕4 = 0011⊕0100 = 0111(十进制7). 这时候并不能从 0111 中直接拆出 3 和 4 了.
那么接下来的思路就是想办法把 3 和 4 区分开来. 在区分一个数是奇偶数时, 我们通过用 &1 操作, 这里我们也可以用类似的方法, 具体来说, 对于两个数字异或的结果, 从二进制低位开始, 找到第一位为 1 的(也就是原来两个数字中不同的那一位), 用它就可以区分开两个数了.
看个例子更直观一点:
要区分 0100 (4) 和 1100 (6), 我们只需要从二进制的低位到高位依次看, 找到第一位不同的, 在这里就是最高的那位, 记为 1000. 然后用 1000 分别和两个数做 &, 0100 & 1000 = 0000, 1100 & 1000 = 1000, 通过 & 的结果, 一个为0 ,另一个不为0 ,就可以区分开.
那怎么找第一位不同的呢? 别忘了我们之前做过异或, 0100⊕1100 = 1000, 这样就可以从低到高扫描了.
上代码:

public int[] FindNumsAppearOnce (int[] array) {

        // 先将全部数进行异或运算，得出最终结果
        int tmp = 0;
        for(int num: array){
            tmp ^= num;
        }

        // 找到那个可以充当分组去进行与运算的数
        // 从最低位开始找起
        int mask = 1;
        while((tmp&mask) == 0){
            mask <<= 1;
        }

        // 进行分组，分成两组，转换为两组 求出现一次的数字 去求
        int a = 0;
        int b = 0;
        for(int num:array){
            if((num&mask) == 0){
                a ^= num;
            }else{
                b ^= num;
            }
        }
        // 因为题目要求小的数放前面，所以这一做个判断
        if(a > b){
            int c = a;
            a = b;
            b = c;
        }
        return new int[]{a,b};
    }