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

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

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

常规方法

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

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

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

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

使用哈希方法解决这两个问题的时间复杂度为 $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 的比特。感兴趣的同学可以自行写几个数找找规律验证一下。关于补码的知识可以阅读“符号数的表示：彻底弄清原码、反码、补码的关系”一文。

本文地址：https://www.jeddd.com/article/single-number-algorithm.html