我被要求从 Python 中的数字列表中找出仅在列表中出现一次的数字。像往常一样,我可以使用立即出现的正常方法轻松解决它:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in nums:
if(nums.count(i) == 1):
return i
return nums[0]
为了寻找另一种更好的方法,互联网建议我使用按位异或运算,并提供了以下代码,该代码更快、更高效。下面是代码:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = 0
for i in nums:
a^=i
print(a)
return a
逻辑是,如果我们对 2 个相同的位(0,0 或 1,1)进行 XOR 运算,则答案将始终为 0,如果位不同,则答案将为 1。利用这一点,就想出了这样一个办法。
我的思绪陷入了试图理解异或运算的正常概念在这里如何发挥作用的过程中。我理解他们所说的关于相同和不同位的逻辑,但是通过他们的代码,每次我与下一位执行异或时,都会弹出一个新数字,那么我们如何保证只有出现一次的数字才会演变?
我感觉毫无头绪。发布代码片段然后要求解释可能不是一个好方法,但我觉得这个解决方案非常有趣,并且非常想了解按位异或如何提供帮助!如果有人有想法,请帮忙!提前致谢。
注意:在列表中,除 1 外,所有数字都出现两次。
此 XOR 解决方案的一般约束有点不同:
您有一个列表,其中恰好有一个数字出现奇数次,而所有其他数字出现偶数次,并且需要找到odd one.
如果这些位相同,则 XOR 翻转这些位:
b1 XOR b1 > b0
b0 XOR b0 > b0
b1 XOR b0 > b1
b0 XOR b1 > b1
您有一个任意的起始值(列表中的第一个数字),例如:
01010111011111101
如果所有其他数字出现偶数次,则每个位模式至少会看到两次。
第一次你有成对的位和
- 每 0,1 位翻转为 1
- 每 1,0 位翻转为 1
- 每 1,1 位翻转为 0
然后你再次遇到相同的数字(因为数字出现偶数次):
- 上次翻转时有 1 位,再次遇到 1 位,因此翻转为 0
- 上次翻转后有 1 位,再次遇到 0 位,因此保持为 1
- 上次翻转后有一个 0 位,再次遇到 1 位,因此翻转为 1
现在你又回到了原来的数字,因为偶数次出现的数字会相互抵消:
101010010
xor 101010010
-------------
000000000
如果您将任何其他数字与 000000000 进行异或,您将准确地得到另一个数字。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)