题目一(数组中只出现一次的两个数字)

一个整形数组里除两个数字之外，其他数字都出现了两次。请找到这两个只出现一次的数字。要求时间复杂度为 O(n)，空间复杂度为 O(1)。

算法思路

题目限制了复杂度，因此常见的思路，如使用哈希表记录数字出现次数、或对每个数字遍历数组计算次数，都不可行。
那么，就要另寻思路。假设，题目变成，一个整形数组里除一个数字之外，其他数字都出现了两次。请找出这一个只出现一次的数字，那么如何求呢？我们想到了异或运算。因为0=a异或a，那么数组中出现两次的数字都会通过异或运算而抵消，所以最好仅留下一个数字，就是那个只出现一次的数字。

那么，回到本题。如果我们能够根据某种标准将数组划分为两个子数组，并且每个子数组中都含有唯一的一个只出现一次的数字，那么我们就可以利用上面的思路进行求解。当对原数组的所有元素进行异或运算后，得到一个结果数字，且由于这两个数字不同，因此异或得到的结果数字的二进制表示中至少有一位是 1，然后，我们找到结果数字中第一个为 1 的位置，记为第 n 位，再以第 n 位是不是 1 为标准把原数组分成两个子数组。这样一来，数字相同的必然都分配到同一子数组中，因为，他们的二进制表示的每一位都是相同的。最后，对子数组分别进行异或运算就可以得到这两个所求的数字了。

算法实现

题目二(数组中唯一只出现一次的数字)

在一个数组中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

算法思路

现在题目是重复的数字出现了三次，那么异或运算就不行了，需要另寻它路。
如果仍然从位运算的角度考虑，可以发现：如果一个数字出现三次，那么它的二进制表示的每一位(0 或者 1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被 3 整除。如果每一位的和都能被 3 整除，那么那个只出现一次的数字的二进制表示中对应的那一位是0；否则就是 1 (不可能是 2，二进制位只有 0、1)。

算法实现

参考

[1] <<剑指offer2>>
[2] 牛客网