本文讨论了leetcode 137——signle number，的通用解题方法。主要参考了该题讨论区的回答，英文较好的同学建议阅读原文。

问题

Leetcode 137. Single Number II的问题描述如下：

已知有一个非空的数列，数列中的元素，除了一个只出现1次，其他元素均出现3次，找出那个只出现一次的元素。

举例： Input: [2,2,3,2] Output: 3

如果不考虑空间复杂度，问题就很简单：我们只需要遍历所有的元素，用一个哈希表记录所有元素出现的次数，输出出现次数为1的元素，但这种方法的空间复杂度为 $O(n)$。这道题有趣的地方在于，可以使用空间复杂度为 $O(1)$ 的方法解决，即不管输入的数组有多长，只需要恒定数量的额外空间，就可以解决该问题。

简单方法

解决这个问题的分析思路是：我们要想一种优雅的方法，使重复3次的数字相互抵消，最后剩下只出现一次的数字。这里面的难点有两个：

  • 我们必须保证重复数字的抵消操作和数字出现的顺序无关，即不论数字以何种顺序出现，最终抵消的结果应该一致。
  • 如何使用恒定空间保存所有的数字信息。

一个简答的方法是，将所有的数字转化为2进制的表达。接着我们建立一个32位的数组count，count数组的第i个元素记录了所有2进制数字在第i位为1的次数总和。举个简单的例子：

假如数组为[2, 2, 2, 1]那么将数组转化为二进制即为[10, 10, 10, 1]。我们遍历数组，记录数组每一位的总和，得到：count[0] = 1, count[1] = 3。这里我们不难发现，如果把只重复一次的数字从原始数组中去掉，那么count数组中每个元素都必然可以被3整除。因此只需要求count数组中所有元素除以3的余数，就实现了对于重复3次数字的相互抵消。

具体代码如下：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            count = 0
            # count 1 bit on ith  
            for num in nums:
                if (num >> i) & 1:
                    count += 1
            
            ans |= (count % 3) << i
        
        # if ans > 2**31, it must be a negative number
        return ans if ans < 2**31 else ans - 2**32

该方法可以从重复3次扩展到重复n次，处理思路相同。

位操作方法

上面的方法已经能够很好的解决这个问题，但我们还可以使用简单的位操作进一步优化，使算法更加简洁优雅。

我们先考虑一种简单的情况，即数列中的元素都重复两次，只有一个重复一次，找出重复一次的元素，代码如下：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for num in nums:
            ans ^= num
        
        return ans

方法及其简单，只需要对每个数依次进行XOR操作，即可获得最终的答案。在这里我们利用的异或的几个重要特性：

  • 改变异或操作的顺序并不影响结果，即 A XOR B XOR C = B XOR C XOR A
  • A XOR 0 = A
  • A XOR A = 0

由于相同的数进行异或会变为0，导致所有重复两次的数全部抵消为0，最终只剩下出现一次的数。

当所有元素重复3次时，简单的异或显然无法得到最终的解，我们需要在之前思路的基础上，进行简单的构造，具体代码如下：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        one = two = 0
        for num in nums:
            one = (one ^ num) & ~two
            two = (two ^ num) & ~one
        
        return one

虽然位操作的运算看起来比较复杂，但是核心的思路很简单：

  • one中保存了所有出现一次的数的异或结果
  • two中保存了所有出现二次的数的异或结果

举个简单的例子，假设数字5连续出现3次：

第一次、one = 5, two = 0

第二次、one = 0, two = 5

第三次、one = 0, two = 0

构造的原理

首先我们需要回答一个问题：为什么当元素重复2次时，我们只需要构造一个数，而元素重复3次时，我们需要构造两个数？

虽然我们只需要输出出现一次的元素，但在整个遍历过程中，需要保存所有的中间状态信息。虽然遍历结束时，仅有2种状态（出现一次、出现三次），但在遍历的过程中，其实存在三种状态（出现一次、出现两次、出现三次），所以必须构造第二个数，如果仅仅用一个数保存所有的状态会导致信息的丢失。以此类推，如果元素重复了 n 次，我们需要构造 n - 1 个数。

现在进一步解释位操作表达式，其过程如下：

  • 当接收一个新的数字时，我们先对其进行XOR的操作
  • 假如该数字出现的次数与我们构造的情形不符，则清除上一步操作

举个简单的例子，当5第三次出现时，one会先做一个XOR操作，将5的信息保留下来，然后发现5是第三次出现，必须撤销上一步的XOR操作。XOR操作的逻辑是在字节为0的位不变，为1的位取反；因为该数的信息保存在two中，我们只需要做& ~two，就可以达到撤销之前操作的目的。