原始问题陈述如下：
给定一个32位无符号整数数组，其中每个数字都出现两次，除了其中三个数字只出现一次。在O(n)时间内使用O(1)额外空间找到这三个数字。输入数组是只读的。如果有k个例外情况而不是3个呢？
如果您接受由于输入限制（数组最多可以有2^33个条目）而导致非常高的常数因子，则可以很容易地在Ο(1)时间和Ο(1)空间内解决此问题。
因此，为了回答这个问题，让我们放弃位数限制，集中在更一般的问题上，其中数字可以具有多达
现在，我想到的方法是不仅计算元素的异或值，还计算应用某个函数后的值的异或值（我选择了
现在，虽然以下算法对于k >= 7不正确，但我仍然包括实现方式以给您一个想法：
根据我的分析，这段代码的最坏时间复杂度为
当然问题在于是否有一种正确、高效的方法具有良好的渐进运行时间（假设这里的
编辑：现在证明上述算法是不正确的，当然希望看到它如何能够变得正确，可能需要降低一些效率。空间复杂度应该小于
给定一个32位无符号整数数组，其中每个数字都出现两次，除了其中三个数字只出现一次。在O(n)时间内使用O(1)额外空间找到这三个数字。输入数组是只读的。如果有k个例外情况而不是3个呢？
如果您接受由于输入限制（数组最多可以有2^33个条目）而导致非常高的常数因子，则可以很容易地在Ο(1)时间和Ο(1)空间内解决此问题。
for i in lst:
if sum(1 for j in lst if i == j) == 1:
print i
因此，为了回答这个问题，让我们放弃位数限制，集中在更一般的问题上，其中数字可以具有多达
m位。
对k = 2进行算法泛化，我考虑以下内容：
- 将那些最低有效位为
1和那些为0的数字分别进行异或。如果对于两个分区，结果值都不为零，则我们知道我们已将非重复数字分成了两组，每组至少有一个成员。 - 对于每个分组，尝试通过检查第二位最不显著的位等来进一步分区。
[0,1,2,3,4,5,6]。现在，我想到的方法是不仅计算元素的异或值，还计算应用某个函数后的值的异或值（我选择了
f(x) = 3x + 1）。有关此附加检查的反例，请参见Evgeny的答案。现在，虽然以下算法对于k >= 7不正确，但我仍然包括实现方式以给您一个想法：
def xor(seq):
return reduce(lambda x, y: x ^ y, seq, 0)
def compute_xors(ary, mask, bits):
a = xor(i for i in ary if i & mask == bits)
b = xor(i * 3 + 1 for i in ary if i & mask == bits)
return a if max(a, b) > 0 else None
def solve(ary, high = 0, mask = 0, bits = 0, old_xor = 0):
for h in xrange(high, 32):
hibit = 1 << h
m = mask | hibit
# partition the array into two groups
x = compute_xors(ary, m, bits | hibit)
y = compute_xors(ary, m, bits)
if x is None or y is None:
# at this point, we can't be sure if both groups are non-empty,
# so we check the next bit
continue
mask |= hibit
# we recurse if we are absolutely sure that we can find at least one
# new value in both branches. This means that the number of recursions
# is linear in k, rather then exponential.
solve(ary, h + 1, mask, bits | hibit, x)
solve(ary, h + 1, mask, bits, y)
break
else:
# we couldn't find a partitioning bit, so we output (but
# this might be incorrect, see above!)
print old_xor
# expects input of the form "10 1 1 2 3 4 2 5 6 7 10"
ary = map(int, raw_input().split())
solve(ary, old_xor=xor(ary))
根据我的分析，这段代码的最坏时间复杂度为
O(k * m² * n)，其中n是输入元素的数量（XOR运算的复杂度为O(m)，并且最多可以成功进行k次分区操作），空间复杂度为O(m²)（因为m是最大递归深度，临时数字可能具有长度m）。当然问题在于是否有一种正确、高效的方法具有良好的渐进运行时间（假设这里的
k << n和m << n完整性的缘故），同时需要很少的额外空间（例如，排序输入的方法不会被接受，因为我们至少需要O(n)的额外空间，因为我们不能修改输入！）。编辑：现在证明上述算法是不正确的，当然希望看到它如何能够变得正确，可能需要降低一些效率。空间复杂度应该小于
o(n*m)（即，总输入位数的亚线性）。如果这使任务更容易，可以将k作为附加输入。
O(1)，但我认为因为2^32 >= N，所以声称你的解决方案是O(N^2)是合理的。就像在这个领域中，O(2**32N)>=O(N^2)[稍微滥用一下O符号]。 - cmh