40、数组中只出现⼀次的数字

题⽬描述

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

示例输入：[92,3,43,54,92,43,2,2,54,1] 输出：3，1

使⽤ hashmap 存储数字出现的次数， key 为出现的数字， value 为该数字出现的次数。遍历⾥⾯所有的数字，如果 hashmap 中存在，那么 value （次数）+1，如果 hashmap 中不存在,那么 value 置为1。

遍历完成之后，需要将次数为 1 的数字捞出来，同样是遍历 hashmap，由于只有两个满⾜条件，我们设置⼀个标识变量，初始化为1，如果找到第⼀个满⾜条件的数字，除了写⼊放回数组中，还需要将该标识置为 2，表示接下来找的是第 2 个。

如果找到第 2 个，那么写⼊之后，直接 return 。

先对数组排序，然后遍历查找不连续的数字。排序后相同的数字会相邻，遍历找到不连续的数字

⾸先需要了解⼀定位运算知识，异或是指⼆进制中，⼀个位上的数如果相同结果就是0，不同则结果是0.

也就是如果⼀个数的最低位是0，另⼀个数的最低位是0，那么异或结果的最低位是0；如果⼀个数的最低位是0，另⼀个数的最低位是1，那么异或结果的最低位是1。

异或操作可以交换，不影响结果：A^B^C = A^B^C

A^A=0,任何⼀个数异或⾃身，等于0，因为所有位都相同

A^0 = A，任何⼀个数异或0，等于⾃身，因为所有位如果和0不同，就是1，也就是保留了⾃身的数值

假设⾥⾯出现⼀次的两个元素为 A 和 B，初始化异或结果 res 为0，遍历数组⾥⾯所有的数，都进⾏异或操作，则最后结果 res = A^B 。

但是我们拿到这个 A 和 B 异或之后的结果，怎么区分呢？

有⼀种巧妙的思路，因为 A 和 B 的某⼀位不同才会在结果中出现 1，说明在那⼀位上， A 和 B 中肯定有⼀个是 0，有⼀个是 1 。

那我们取出异或结果 res 最低位的1，假设这个数值是 temp （temp只有⼀个位是1，也就是A和B最后不同的位）

遍历数组中的元素，和 temp 进⾏与操作，如果和 temp 相与，不等于0。说明这个元素的该位上也是1。那就说明它很有可能就是 A 和 B 中的⼀个。

只是有可能，其他的数也有可能该位上为 1 。但是符合这种情况的，其他数肯定出现两次，⽽ A 和 B只可能有⼀个符合，并且只有可能出现⼀次 A 或者 B 。

凡是符合和 temp 相与,结果不为0的，我们进⾏异或操作。

也就是可能出现， res1 = B^C^D^C^D…^E^E^B 或者 res1 = A^C^D^C^D…^E^E 。

上⾯的式⼦可以视为 res1 = B 或者 res1 = A

这样操作下来，我们就知道了 res1 肯定是其中⼀个只出现⼀次的数（ A 或者 B ）,⽽同时上⾯计算出了 res = A^B ,也就是可以通过 res1^res 求出另⼀个数。

通过示例详细解释算法过程：

输入：[92,3,43,54,92,43,2,2,54,1] 单次数：3 和 1

步骤1：计算所有数字的异或结果

步骤2：找到异或结果的最低位的1

步骤3：根据最低位1分组

步骤4：分别异或各组

位运算特性利用：