给定一个整数数组，其中每个数字出现三次，除了一个数字出现两次，找到出现两次的数字？

Question

这是 "Elements of programming interview" 提出的问题。我看到这个问题 posted here 但接受的答案（或其他答案）不完整。

使用在 base 3 系统上运行的类似 XOR 的操作（在 post 中称为 xor3），您得到的结果是 x xor3 x。但是，问题是得到x。 xor3 定义为加法模 3（其中数字以 3 进制表示）

我们如何从 x xor3 x 中获取 x 部分？

Answer 1

如果您再次遍历数字数组会怎样？假设第一次迭代后的值为 a = x xor3 x

遍历数组中的所有条目，xor3 每个值 a。

for y in arr:
    if y xor3 a == 0:
        print y
        break
    else
        continue

目前我认为这是天真的解决方案。考虑到每个 xor3 作为 O(1) 和 O(1) 内存，这仍然是 O(n)。