本文来看两个相似的算法题:

  1. 给定一个整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出只出现了一次的那个元素,返回该元素。(LeetCode 136. Single Number
  2. 给定一个整数数组,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素,返回这两个元素组成的 vector。(LeetCode 260. Single Number III

两个题目十分相似,区别仅在于第一题是找一个元素,第二题是找两个元素。

常规方法

对于采用多层循环的暴力解法,本文不做叙述。这里说的常规方法是一种容易想到的且合理的方法。

对于这两道题,比较容易想到的方法是使用哈希表:遍历整个数组,对于每个元素,若其不在哈希表中,则将该元素加入哈希表;若其已经在哈希表中了,则将其从哈希表中移除。

由于除了要找的元素外的其他元素都恰好出现两次,那么所有出现两次的元素都会经历“被加入哈希表”、“从哈希表中移除”两个步骤。因此,在遍历完整个数组后,哈希表中剩下的就是要找的只出现一次的数字了。

这里,使用哈希表而不是其他数据结构(如查找树)是因为哈希表可以在 $O(1)$ 时间内完成一个元素的查找、插入和删除。本题中,只需要判断元素是否在哈希表中,而无序对元素进行映射,因此可以使用 C++ STL 的 unordered_set<int> 数据结构,需要用到该结构的 findinserterase 方法。

使用哈希方法解决这两个问题的时间复杂度为 $O(n)$,空间复杂度为 $O(n)$。

“异或”方法

使用更巧妙的方法能够提高算法性能。能想到这种方法,需要对位运算的性质特别熟悉。异或的数学符号是 $\oplus$,在编程语言中的运算符通常是 ^

异或运算的基本特点是,对于两个比特(二进制位),若它们相同则异或结果为 0,若不同则结果为 1。异或运算的真值表如下:

$a$$b$$a\oplus b$
000
011
101
110

现考虑具有多个比特位组成的整数 $a$ 。若两个整数相等,那么它们的每一个比特位都相同,因此按位异或起来的结果就是 0;两个不等的整数进行异或运算的结果一定不是 0,因为这两个整数至少在一个比特位上不同。此外还有一条重要性质:任何一个整数和 0 异或的结果就是这个整数本身。这两条性质用数学公式表示如下:

  • $a\oplus a=0$
  • $0\oplus a=a$

下面,我们把异或的这些性质作用于这两道题上。

找一个元素

异或运算符和交换律和结合律,即 $a\oplus b\oplus a=(a\oplus a)\oplus b=0\oplus b=b$。

如果我们把数组中的所有元素异或起来,那么出现两次的数字都相互抵消为 0,最终剩下的结果就是那个唯一的出现了一次的元素。提示一点,下面的代码把 result 初始化为 0,是因为任何数异或 0 的结果还是原来那个数,因此可以作为初始值。

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;
}

上面代码的第 3 行用到了范围 for 语句,需要 C++11 的支持。

时间复杂度为 $O(n)$,空间复杂度为 $O(1)$。尽管时间复杂度与之前采用哈希表的方式相同,但使用异或更加简单,免去了创建哈希表、插入和删除元素的操作,性能更好。

找两个元素

找两个元素比找一个元素要更复杂一些,不过思路仍然是利用异或运算的特殊性质。

假设要找的两个数字分别是 $x$ 和 $y$,如果仍然按照之前的方法,把数组中的所有元素全部异或起来,那么得到的结果是要找的两个数异或后的结果 $x\oplus y$,但无法将两个数分离出来。我们要做的,是想办法把原数组分为两部分,使得第一部分包含 $x$,第二部分包含 $y$。如果能找到这样的分法,那么问题就转换为了在每个部分中找一个元素,而找一个元素的算法我们已经在第一题中解决了。

再次考虑异或的性质。对于异或结果中为 1 的比特,原数在这个比特位上的值一定是不同的。因此如果我们能找到 $x\oplus y$ 这一结果中任何一个为 1 的比特,就可以根据该比特位上的值是 1 还是 0 把原数组分为两部分了。

如何找到 $x\oplus y$ 中为 1 的比特?可以初始化一个掩码 mask 为 1,然后通过不断左移 mask 的方法来找到最右边的为 1 的比特。

之后,重新遍历原数组,并根据每个元素在刚刚找到的比特位上为 1 还是 0 分别应用“找一个元素”的方法即可。

vector<int> singleNumber(vector<int>& nums) {
    int temp = 0;
    for (int num : nums) temp ^= num;
    
    int mask = 1;
    while ((mask & temp) == 0) mask <<= 1;  // 找到最右边的为1的比特
    
    int x = 0, y = 0;
    for (int num : nums) {
        if (num & mask) x ^= num;
        else y ^= num;
    }
    
    return {x, y};
}

其实,如果你的计算机底层原理掌握的比较好,就可以知道上面代码的第 5、6 行可以进一步简化为:

int mask = temp & (-temp);  // 找到最右边的为1的比特

通过对整数与其相反数进行逻辑与运算(AND),就可以得到这个整数最右边的为 1 的比特。感兴趣的同学可以自行写几个数找找规律验证一下。关于补码的知识可以阅读“符号数的表示:彻底弄清原码、反码、补码的关系”一文。