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。

Leetcode单数II算子解法讲解

Leetcode Single Number II Operator Solution Explanation

algorithm

operators

bitwise-operators

data-structures