在长度为n的序列中，其中n = 2k + 3，即有k个唯一数字出现两次，而三个数字仅出现一次。
问题是： 如何找到只出现一次的三个唯一数字？
例如，在序列1 1 2 6 3 6 5 7 7中，三个唯一数字是2 3 5。
注意：3 <= n <1e6，该数字范围为1到2e9
内存限制：1000KB，这意味着我们无法存储整个序列。
我尝试过的方法（超过内存限制）：
我初始化一棵树，当读入一个数字时，我尝试将其从树中删除，如果remove返回false（未找到），则将其添加到树中。最后，树具有三个数字。可以，但是超出了内存限制。
我知道如何使用位操作找到一个或两个这样的数字。所以我想知道
我们可以使用相同的方法（或某些相似的方法）找到三个？
查找一个/两个数字的方法仅出现一次：
如果一个数字只出现一次，我们可以对序列进行异或运算以找到它。
如果有两个，我们可以先对序列应用XOR，然后按结果的1位将序列分为2个部分，然后对2个部分再次应用XOR，我们将找到答案。
您可以使用与一个和两个不同值的较简单情况类似的方式进行此操作。
每个数字位（例如32位）需要两个整数。对于每个数字，如果该位为零，则将第一个整数与其异或。如果不是，则将第二个整数与其异或。
另外，请记下在每个位置找到1或0的次数（我们只需要检查这是偶数还是奇数，因此请保留布尔值）。
迭代之后，我们的整数对将是以下之一。这里的第一个数字表示偶数，第二个数字表示奇数。
0, a^b^c a^b, c a^c, b b^c, a
对于每对，检查偶数整数。如果为零，则我们知道另一个整数是a ^ b ^ c，因为我们的结果中没有两个相等。否则，我们会在奇数计数整数处找到一个值。
public static int[] find3(int[] list) { int[][] xors = new int[32][2]; boolean[] counts = new boolean[32]; for (int curr : list) { for (int i = 0; i < 32; i++) { xors[i][(curr & (1 << i)) >> i] ^= curr; counts[i] ^= ((curr & (1 << i)) == (1 << i)); } } // this really shouldn't take so many lines int[] ret = new int[3]; int found = 0; for (int i = 0; i < 32; i++) { int oddCount = xors[i][counts[i] ? 1 : 0]; int evenCount = xors[i][counts[i] ? 0 : 1]; if (evenCount != 0) { // avoid the 0, a^b^c case. if (found == 0) { ret[0] = oddCount;// a ret[2] = evenCount;// b^c for now found++; } else if (found == 1 && ret[0] != oddCount) { ret[1] = oddCount;// b ret[2] ^= oddCount;// (b^c)^b == c break; } } } return ret; }
