algorithm - Leetcode Single Number II Operator 解决方案说明

Question

关闭。这个问题需要更多focused .它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post .

去年关闭。




Improve this question




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

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 中多变的。如果出现 3 次，它将不会存储在任何变量中，因为如果我们多次将整数传递给函数，(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 .