题目描述
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
题解一
先将数组排序，然后再找出现一次的数字是比较简单的。
时间复杂度为，空间复杂度为
。比较简单，代码省略。
题解二
还有一种想法是以空间换时间，使用一个哈希表来记录数组中每个数字出现的次数，最终可以得到两个只出现一次的数字。
时间复杂度为，空间复杂度为
。比较简单，代码省略。
题解三
重头戏来了，我们可以在时间复杂度为的情况下，将空间复杂度降低至
。如果将这道题改为数组中只有一个数字只出现一次，那么问题就简单了。我们可以利用异或运算（相同为0，不同为1）的性质：
- 任何一个数字异或它自己都等于0。
- 异或运算具有交换律。
因此，如果我们依次遍历异或数组中的每个数字，那么最终出现的结果就是那个只出现一次的数字（因为其他相同的数字进行异或运算之后都是0，全部抵消了）。
但是由于这道题中有两个数字只出现一次，所以问题会复杂一点，但是我们依旧可以将它化解为一个数字的情形。只要将原数组拆成两个数组，每个数组都包含一个只出现一次的数字即可。
我们还是从头到尾一次遍历异或数组中的每个数字，最终会得到那两个只出现一次的数字的异或结果。而这个结果的二进制表示中至少有一位为1，假设我们在结果中找到第一个为1的位的位置，记为index，那么就可以对于所有数字按照这个位是否为1划分为两部分。
建立两个数组，分别保存拆成两个数组之后的结果。因为那两个只出现一次的数在index位上异或结果为1（对于异或，相同为0，不同为1），说明这两个数在index位上是不一样的。
使用这个判断条件，可以将整个数组分为两类。第一类子数组中每个数字的index位都为1，第二类子数组中每个数字的index位都为0。这样同时也将两个只出现一次的数给分开了，而且同时保证相同的数处于同一个数组中（相同的数index位一定相同）。为了方便实现，我自己写了个getFullBinaryString()函数。
得到两个数组之后，我们就将这个问题转化为求数组中一个数字出现一次的问题了。
时间复杂度为，空间复杂度为
。
这样说有点抽象，举个例子，假设输入的数组为{1,2,10,4,1,4,3,3}，依次对数组中每一个数字进行异或运算之后，得到的二进制结果为1000。第一位为1，于是我们将index设置成1，我们根据每个数字的index位是否为1将数组分为两部分，分别得到两个数组 和 。接下来分别对两个数组求异或就可以得到两个只出现一次的数字2和10了。
下面是参考代码：
import java.math.BigInteger;
import java.util.*;
class Solution {
public int[] singleNumbers(int[] nums) {
// 得到两个只出现一次的数字的异或结果
int resXOR = 0;
for (int num : nums)
resXOR ^= num;
String resXORString = getFullBinaryString(resXOR);
// 计算第一个为1的位的位置，据此将原数组划分为两个数组
int index = 0;
for (int i = 1; i < 32; i++) {
if (resXORString.charAt(i) == '1') {
index = i;
break;
}
}
// 划分数组
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
for (int num : nums) {
String numString = getFullBinaryString(num);
if (numString.charAt(index) == '1')
list1.add(num);
else list2.add(num);
}
return new int[] {findUnique(list1), findUnique(list2)};
}
public int findUnique(ArrayList<Integer> list) {
int res = 0;
for (int num : list) {
res ^= num;
}
return res;
}
public String getFullBinaryString(int num) {
String s = Integer.toBinaryString(num);
return String.format("%032d", new BigInteger(s));
}
}
