题解 | #数组中只出现一次的两个数字#

40、数组中只出现一次的两个数字

方法一：

题目给的意思分析之后，很容易想到一种方法，就是用哈希表辅助得到这两个只出现一次的数字。

代码思路：

1、创建一个哈希表

2、当数组元素没有在哈希表中成为key的时候，put进哈希表，当已存在的时候，则remove掉。

3、最后哈希表中剩下的key就是只出现一次的数字

4、遍历key然后返回结果

直接贴出代码：

public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        // 用于返回结果
        int[] res = new int[2];
        // 创建一个哈希表
        HashMap<Integer,Object> set = new HashMap<>();
        for(int i = 0; i < array.length; i++){
            // 如果已经被当作key了，那就直接remove掉
            if(set.containsKey(array[i])){
                set.remove(array[i],null);
            }else{
                // 否则就添加进去
                set.put(array[i],null);
            }
        }
        int i = 0;
        // 最后拿出来放进返回结果的数组中进行返回
        for(Integer num:set.keySet()){
            res[i++] = num;
        }
        return res;
    }

这个方法非常常规，容易想到并且也容易实现。但是它的时间复杂度和空间复杂度都是O(N)。

那么，如果给这道题目加上一个限制（用O(1)的空间复杂度实现），也就是说不能用哈希表做了，我们还能想到其它的思路吗？

所以，下面我们就用空间复杂度为O(1)的做法来解决这道题目吧~

方法二：位运算

对于这道题目，我们先来想另外一个问题：

如果数组中只有一个出现了一次的数字，我们想到得到它，那么应该如何解决呢？

我们都知道异或运算：如果两个数一样则异或结果为0，不一样则异或结果为1。（二进制）

（0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0）

举个例子：

4 ⊕ 4 = 0，将4化为二进制为 0100

所以 0100

异或 0100

得到 0000

4 ⊕ 4 ⊕ 5 = 5

则 0100

​ 0100

​ 0101

得到 0101

我们可以看到上面的运算过程，因为4=4，两者相等异或结果为0。所以0异或任意数都等于任意数。

所以，当只有一个出现了一次的数字的时候，则只需要将全部数进行异或运算，运算结果就剩下了那个只出现一次的数字了。

public int[] singleNumber(int[] nums) {
    int x = 0;
    for(int num : nums)  // 1. 遍历 nums 执行异或运算
        x ^= num;
    return x;            // 2. 返回出现一次的数字 x
}

好了，上面说了这么多，那这道题目是找两个只出现一次的数字呀~

上面的方法又是针对只出现一次的数字，假设我也一样全部执行异或运算 1⊕4⊕1⊕6，最后也还是会剩下4⊕6呀~

我们看看：

0100 ⊕ 0110 = 0010 这个结果也不能得出什么东西哇~

我们换个角度思考，能不能做个分组，将题目分为两组 ，然后每一组求出其中的出现一次的数字，最后两者一起返回，不就解决问题了吗？

那么我们要如何分组呢？位运算进行分组，我们首先想到的应该是奇偶分组，就是将所有数 &1，此时能将数字分为奇偶两组。

但是这个时候问题又来了，你又不能保证两个数字就一奇一偶，有可能都是奇数也有可能都是偶数呀~

但是，我们想一下，&1的操作，归根到底，是按照二进制最低位的不同来分组的，

例如 ： 0011（3） ，0101（5），0100（4），0001（1）

对上面四个数分组，我们都&1，可以分得结果： 0011，0101，0001（奇数） 0100 （偶数）

我们很明显能够知道，当二进制&1结果为1的时候，为奇数，反之为偶数。它们是按照最低位的不同来分组的。

上面我们知道，能够将数字分为 奇偶两组，那么现在，我再给出一个难度，如何区分出 0011，0101 ？

对 0011，0101 这两个数进行分组，我们可以观察到最低位都为1，此时如果我们还是进行&1操作去分组，那肯定是分不出来的！

因为两数的最低为都是一样的，&1之后还是1，还是无法区分，那么我们看到最低的第二位0011是1，0101是0，很明显这两位就不一样，那么我们就可以将这两数&0010呀，不就能够区分出来了吗？

0011 &0010 = 0010 0101&0010 = 0000，此时还是根据结果是否为0得到分组！

那要是是 0100 和 1100呢？如何分组呢？ 不就是&1000 就能够分组了吗？

所以，说了那么多，其实就是为了推出一个分组的方式，两个不同的数如何分组！

我们都知道两个不同的数，那么它的二进制表示肯定是不一样的！这是毋庸置疑的！

所以，我们要想对两者进行分组操作，就是需要找到两者中的那一位不同的二进制，然后得到分组的与值（去&的那个值），问题不就解决了吗？

那要怎么找到那一位不同的二进制呢？

我们看一个例子： 1，1，4，6

全部做异或运算结果为 4⊕6 = 0100⊕0110 = 0010

异或的运算规则是什么？ 相同的为0，不同的为1。所以我们根据两者异或出来的结果 0010，不就可以知道那一位不同了嘛？（为1的那一位就是不同的）

好了，说了这么多，下面安排代码把~

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};
    }

复杂度分析：

时间复杂度：O(N)。数组的长度n，循环。

空间复杂度：O(1)。几个变量的空间。