key: 38 title: 只出现一次的数字
这里分享三道寻找数组中只出现一次的数字的问题. 这些题使用哈希表都很好做, 但这里我们使用位运算, 可以很巧妙地在常数空间复杂度内解决问题.
题目源自 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]注意：
- 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
- 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
这道题变成了有两个数字只出现一次. 怎么解呢? 如果我们将数组里的元素全部异或, 得到的结果应该是这两个只出现一次的数字的异或. 可是怎么从异或的结果还原出这两个数字呢?
别忘了异或运算的特性: 异为真同为假. 首先, 这两个只出现一次的数字必然是不相等的, 因此异或的结果至少有一个二进制位为 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 = 01 @ 0 = 10 @ 1 = 11 @ 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
参考资料: