列表中的单个元素

Question

我是python的新手,我发现这个代码在列表中找到一个元素

这是代码:

def single_number(arr):
    ones, twos = 0, 0
    for x in arr:
        ones, twos = (ones ^ x) & ~twos, (ones & x) | (twos & ~x)
    assert twos == 0
    return ones
arr1 = [5, 3, 4, 3, 5, 5, 3]
print(single_number(arr1))

我似乎无法理解线路在做什么

ones, twos = (ones ^ x) & ~twos, (ones & x) | (twos & ~x)
assert twos==0

Answer 1

该行的目的是实现一个操作,如果输入应用三次,则返回原始值,如果应用一次,则保留输入.

如果我们想从包含对而不是三元组的数组中选择单个值,则更容易理解.那我们就可以......

ones = ones ^ x

...因为y ^ x ^ x == y.所以所有对都取消了,你留下了单值.

正如其他人评论的那样,三项案例是一个非常讨厌的模糊黑客,只有在性能至关重要且问题非常具体时才能使用.

我认为断言只是试图确认满足前提条件,即所有数字都是三元组,除了一条.这不是故障安全的.

Answer 2

你不会想这样做，除非你真的内存空间有限 - 即使这样，你可能也不应该使用它。

这是某种位移/位操作“魔法”，即

• 不直观
• 摆弄危险
• 不好维护
• 难以理解

计数器的工作时间复杂度为 O(n) - 这就是检查列表中所有元素所能做的最好的事情 - 它只需要一些更恒定的时间（用于设置计数器对象）和一些空间（用于维护内部字典）。转移你发现的东西。

def getSingle(arr):
    from collections import Counter
    c = Counter(arr)

    return c.most_common()[-1]  # return the least common one -> (key,amounts) tuple

arr1 = [5, 3, 4, 3, 5, 5, 3]

counter = getSingle(arr1)

print (f"{counter[0]} occured {counter[1]} time(s)")

输出：

4 occured 1 time(s)