最初的问题陈述是这样的：
给定一个 32 位无符号整数数组，其中每个数字都恰好出现两次，除了其中三个（恰好出现一次），使用 O(1) 额外空间在 O(n) 时间内找到这三个数字。输入数组是只读的。如果有 k 个异常而不是 3 个呢？
如果由于输入限制而接受一个非常高的常数因子，则很容易在Ο(1)时间和空间上解决这个问题（数组最多可以有 2 33个条目）：Ο(1)
for i in lst:
if sum(1 for j in lst if i == j) == 1:
print i
所以，为了这个问题，让我们放弃对位长度的限制，专注于数字最多可以有m位的更普遍的问题。
概括 k = 2 的算法，我想到的是以下内容：
- XOR 那些具有最低有效位的数字
1和那些分别具有的数字0。如果对于两个分区，结果值都不为零，我们知道我们已经将不重复的数字分成了两组，每组至少有一个成员 - 对于这些组中的每一个，尝试通过检查第二低有效位来进一步划分它，依此类推
不过，有一个特殊情况需要考虑。如果在划分一个组之后，其中一个组的 XOR 值都为零，我们不知道得到的子组之一是否为空。在这种情况下，我的算法只是忽略了这一位并继续下一个，这是不正确的，例如它对 input 失败[0,1,2,3,4,5,6]。
现在我的想法是不仅要计算元素的 XOR，还要计算应用某个函数后的值的 XOR（我在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输入元素的数量（异或是O(m)，最多k分区操作可以成功）和空间复杂度O(m²)（因为m最大递归深度和临时数字可以是长度m）。
问题当然是是否存在具有良好渐近运行时的正确k << n、有效的方法（为了完整起见，我们假设m << n这里），它也需要很少的额外空间（例如，对输入进行排序的方法将不被接受，因为我们至少需要O(n)额外的空间，因为我们不能修改输入！）。
编辑：既然上面的算法被证明是不正确的，当然很高兴看到它是如何正确的，可能会降低它的效率。空间复杂度应该是 in o(n*m)（即，在输入比特的总数中是次线性的）。如果这样可以使任务更容易，则可以将其k作为附加输入。