起因于 Single Number
:一个数字在数组中只出现了一次,其它数字都出现了两次,找到这个数字。
def singleNumber(nums):
res = 0
for i in nums:
res ^= i
return res
两个相同的数相与会抵消,最后只会剩下只出现一次的那个数。逻辑上感觉很好理解,但是具体我就容易懵,先暂且记录一下吧。
还有两个数字在数组中只出现了一次,其它出现了两次。
思路是这样:先将所有数字异或一遍,那么最后留下来的数字就是那两个只出现一次数字的异或。
根据这个数而应 2 进制从右边起第一个 1,将原数组拆成 2 份,然后分别异或可以得到结果。
# 大神代码
def singlenumber3(nums):
tmp = singleNumber(nums)
res = [0, 0]
# 得到不同的那一位为 1
mask = tmp &(-tmp)
for i in nums:
if i & mask:
res[0] ^= i
else:
res[1] ^= i
return res
这里想不明白的是 mask = tmp &(-tmp)
是如何得到其二进制最右边的 1?
网友评论