只出现一次的数字

这里分享三道寻找数组中只出现一次的数字的问题. 这些题使用哈希表都很好做, 但这里我们使用位运算, 可以很巧妙地在常数空间复杂度内解决问题.

第一题

题目源自 Leetcode 136 题

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

异或运算的特性是, 异为真同为假. 即 1 ^ 1 = 0, 0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1. 因此, 两个相同的数异或的结果为 0, 任何数与 0 异或的结果都为它自身. 此外, 异或运算还满足交换律. 如果我们将数组里的元素全部异或会得到什么结果呢? 以数组 [4,1,2,1,2] 为例:

  4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ 1 ^ 1 ^ 2 ^ 2
= 4 ^ 0 ^ 0
= 4

因为异或运算满足交换律, 因此我们可以将出现两次的数字移动到一起, 它们异或的结果为 0; 结果就成了只出现一次的数字与 0 异或, 最后结果等于只出现一次的数字. 也就是说, 解这道题我们只需将数组里的元素全部异或就可以了. 代码非常简洁:

def singleNumber(nums):
    return reduce(lambda a, b: a ^ b, nums)

第二题

题目源自 Leetcode 260 题

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

注意：

1. 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

这道题变成了有两个数字只出现一次. 怎么解呢? 如果我们将数组里的元素全部异或, 得到的结果应该是这两个只出现一次的数字的异或. 可是怎么从异或的结果还原出这两个数字呢?

别忘了异或运算的特性: 异为真同为假. 首先, 这两个只出现一次的数字必然是不相等的, 因此异或的结果至少有一个二进制位为 1. 反过来, 如果已知异或结果的第 i 位为 1, 那么这两个数中必有一个第 i 位也为 1. 如果我们遍历数组, 将所有第 i 位为 1 的数字全部异或会发生什么呢? 注意第 i 位为 1 的数要么是这两个只出现一次的数中的一个, 要么就是其它出现了两次的数. 出现两次的数异或结果必为 0. 因此, 将所有第 i 位为 1 的数字全部异或就能得到这两个只出现一次的数中的一个.

异或的逆运算还是异或, 即如果 a ^ b = c 则 a ^ c = b. 因此只需再作一次异或就能得到另一个数了.

至于取异或结果某一个为 1 的二进制位, 我们可以这样做. 一个数与自己的相反数作按位与运算, 即 x & -x, 会保留这个数最右边的 1, 其余位都置为 0. 因为 -x 为 x 的补码, 等于按位取反再加一, 这样最右边的 1 先取反变为 0; 而它右边所有的 0 (如果有的话) 会先取反变为 1, 然后加一全部进位变为 0, 最右边的 1 的位置 (刚刚取反变成 0 了) 进位又变回了 1. 这样 -x 再与 x 按位与, 就只剩下最右边的 1 了. 举个例子:

x   = 101000
-x  = ~x + 1
    = 010111 + 1    # 取反, 最右边的 1 变为 0, 且它右边的 0 全部变为 1
    = 011000        # 加一, 右边 0 取反得到的 1 全部进位

x & -x = 101000 & 011000
       = 001000     # 保留最右边的 1, 其余位都置为 0

最终的代码如下:

def singleNumber(nums):
    xor = reduce(lambda a, b: a ^ b, nums)
    mask = xor & -xor
    k = 0
    for n in nums:
        if n & mask:
            k ^= n

    return [k, k ^ xor]

第三题

题目源自 Leetcode 137 题

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

这道题中, 数组中的数字可能出现一次或三次, 这就没法像前两道题一样使用异或了. 因为一个数与自身异或三次得到的还是它本身, 这就无法与只出现一次的数区分开了.

既然无法使用异或, 我们不妨想想什么样的运算可以满足我们的需求. 假设有一种逻辑运算 @, 有

• 0 @ 0 = 0
• 1 @ 0 = 1
• 0 @ 1 = 1
• 1 @ 1 @ 1 = 0

至于 1 @ 1 的结果, 我们不关心, 它可以是任意值. 这样的运算就能帮助我们解这个问题了. 但遗憾的是这个运算是不存在的 – – 1 @ 1 的值该为多少呢? 如果为 1, 那么 1 @ 1 @ 1 = 1 @ 1 = 1, 不满足需求; 如果为 0, 那么 1 @ 1 @ 1 = 0 @ 1 = 1 也不满足需求. 实际上, 要想 1 @ 1 @ 1 = 0, 这个运算就必须设法对 1 出现的次数计数, 只有 0 和 1 是不够用的.

既然只有 0 和 1 不够用, 那我们就用两个变量 a 和 b, 来对 1 出现的次数计数. 我们可以规定:

1 出现的次数	a	b
0	0	0
1	0	1
2	1	0

我们可以定义 @ 运算接受元组 (a, b) 和位元 n. 它的结果是一个新的元组 (a', b'). 那么就有:

• (0, 0) @ 0 = (0, 0)
• (0, 0) @ 1 = (0, 1)
• (0, 0) @ 1 @ 1 @ 1 = (0, 0)

我们可以列出 @ 运算的真值表:

a	b	n	a’	b’
0	0	0	0	0
0	1	0	0	1
1	0	0	1	0
0	0	1	0	1
0	1	1	1	0
1	0	1	0	0

类似于 “按位与”, “按位异或”, 我们把整数的每一位都执行 @ 逻辑运算, 就是 “按位 @”. 根据真值表我们很快就能写出按位 @ 运算的代码了:

a_ = a & ~b & ~n | ~a & b & n
b_ = ~a & b & ~n | ~a & ~b & n

接下来的做法就跟第一题一样了. 我们只需将数组里的元素全部执行按位 @. 因为当且仅当 b = 1 时 1 出现的次数为 1. 因此我们最后返回 b 即可.

def singleNumber(nums):
    a = b = 0
    for n in nums:
        a_ = a & ~b & ~n | ~a & b & n
        b_ = ~a & b & ~n | ~a & ~b & n
        a, b = a_, b_
    return b

---

参考资料:

• 逻辑电路角度详细分析该题思路，可推广至通解