python - 给定一个数字列表，其中每个数字都出现两次，除了一个。返回该数字

Question

我被要求从 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。利用这一点，就想出了这样一个方法。

我的思绪陷入了试图理解异或运算的正常概念在这里如何发挥作用的过程中!我理解他们所说的关于相同和不同位的逻辑，但通过他们的代码，每次我与下一位执行异或时，都会弹出一个新数字，那么我们如何保证只有出现一次的数字才会被演化？

感觉自己一无所知。发布代码片段然后要求解释可能不是一个好方法，但我觉得这个解决方案非常有趣，并且非常想了解按位异或如何提供帮助!如果有人有想法，请帮忙!提前致谢。

注意:在列表中，除了一个数字外，所有数字都出现两次。

Answer 1

此 XOR 解决方案的一般约束有点不同:

您有一个列表，其中只有一个数字出现奇数次，而所有其他数字出现偶数次，需要找到奇数。

如果位相同，则 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 进行异或，您将准确地得到另一个数字。