题目描述

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

题解一

先将数组排序，然后再找出现一次的数字是比较简单的。

时间复杂度为，空间复杂度为。比较简单，代码省略。

题解二

还有一种想法是以空间换时间，使用一个哈希表来记录数组中每个数字出现的次数，最终可以得到两个只出现一次的数字。

时间复杂度为，空间复杂度为。比较简单，代码省略。

题解三

重头戏来了，我们可以在时间复杂度为的情况下，将空间复杂度降低至。如果将这道题改为数组中只有一个数字只出现一次，那么问题就简单了。我们可以利用异或运算（相同为0，不同为1）的性质：

1. 任何一个数字异或它自己都等于0。
2. 异或运算具有交换律。

因此，如果我们依次遍历异或数组中的每个数字，那么最终出现的结果就是那个只出现一次的数字（因为其他相同的数字进行异或运算之后都是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));
    }
}