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