在数组中查找特殊数字

Question

数组中有许多数字,除了出现一次的一个特殊数字外,每个数字出现三次.这是一个问题:如何在数组中找到特殊数字？
现在我只能提出一些基数排序和快速排序的方法,这些方法无法利用问题的性质.所以我需要一些其他的算法.
谢谢你的帮助.

Answer 1

按位数添加数字mod 3,例如

def special(lst):
    ones = 0
    twos = 0
    for x in lst:
        twos |= ones & x
        ones ^= x
        not_threes = ~(ones & twos)
        ones &= not_threes
        twos &= not_threes
    return ones