【剑指Offer】面试题56-1：数组中只出现一次的两个数字

发表于 | 分类于 | 阅读次数:

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

思路 1：排序后遍历

最直观的思路是：对数组先排序，然后从头到尾遍历，找出只出现一次的数字。但是这种算法的时间复杂度是 $O(n\,log\,n)$。我们需要思考更快的算法。

思路 2：异或

由于数组中绝大多数的数字都是出现两次，我们想要消除掉这些出现两次的数字，很自然的可以想到使用异或操作：相同为 0，相异为 1。但是把数组的所有数字都异或之后，我们最终可以得到的结果是那两个不相同的数字异或的结果。如何将这两个数划分开来呢？我们知道，两个不相同的数字异或的结果肯定不是 0，因此它的二进制表示必然存在某一位等于 1，在这一位上那两个数字中有一个是 0 有一个是 1。因此我们可以将整个数组分为两个类别，一类是这一位是 1 的，另一类是这一位是 0 的，这样就把两个数字划分开了。这时我们再分别对两个类别取异或操作，便能得到两个不同的数字。

总结一下思路：首先把数组中的所有数字进行异或，得到两个不相同数字的异或结果；然后找到这个结果的二进制表示中为 1 的某一位；接着把整个数组按该位为 0 和 1 划分成两类；最后对每一类分别进行异或，便可以得到两个不同的数字。

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// num1, num2 分别为长度为 1 的数组。传出参数
// 将 num1[0], num2[0] 设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int[] array,int[] num1, int[] num2) {
        // 特殊输入的检查
        if (array == null || array.length == 0)
            return;
        if (num1 == null || num1.length == 0 || num2 == null || num2.length == 0)
            return;

        // 异或
        int res = 0;
        for (int a: array)
            res ^= a;

        // 区分位
        int bit = 1;
        while (true) {
            if ((res & bit) > 0)
                break;
            bit <<= 1;
        }

        // 划分开，异或
        for (int a: array) {
            if ((a & bit) == 0)
                num1[0] ^= a;
            else
                num2[0] ^= a;
        }
    }
}