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)。几个变量的空间。