Leetcode 单数 II 运算符解决方案说明

Question

问题是'给定一个非空的整数数组，每个元素出现三次，除了一个，它只出现一次。找到那个。我想出了一个简单的解决方案，但在网上找到了这个解决方案并感到困惑。有人可以解释这段代码，也许可以解释这些运算符的用途以及我们何时应该在提出编码问题解决方案时使用它们。

class Solution:
def singleNumber(self, nums: List[int]) -> int:
seen_once = seen_twice = 0
for num in nums:
seen_once = ~seen_twice & (seen_once ^ num)
seen_twice = ~seen_once & (seen_twice ^ num)
return seen_once

Answer 1

Hung Thai的一条评论中提到了这种方法的粗略想法，但我想进一步阐述它。

变量seen_once和seen_twice用于存储我们遍历数组时发生的元素的值。如果元素出现一次，那么它的值存储在seen_once中，如果它出现两次，那么它存储在seen_twice变量中。如果它出现三次，它将不会存储在任何变量中，因为如果我们多次将整数传递给函数，(seen_once, seen_twice)将具有以下值状态：(0,0) -> (n,0) -> (0,n) -> (0,0) -> ....因此，任何处理到第三次的整数都将变量重置为其初始状态，即(0,0)。 因此，遍历整个数组后我们在seen_once元素中获得的值将是我们的答案。

让我们取一个数组：{2, 2, 2, 3}

seen_once = 00, seen_twice == 00

当我们在第一个元素即 2 时，它的二进制表示将10。

现在seen_once will be (~00)&(00^10) = 10 which is 2的价值。 以及seen_twice will be (~10)&(10^10) = 00的价值.

因此，seen_once存储 2，因为它到目前为止只发生过一次，seen_twice为 0。

当我们进一步遍历时，我们再次得到 2，因此到目前为止已经发生两次的seen_twice will become 2值和seen_once will become 0的值。

然后我们第三次得到2。现在，两个变量的值都将变为 0。

最后，我们得到3，它只发生过一次，所以它将存储在seen_once.

循环结束后，我们得到的答案是seen_once = 3.