相关疑难解决方法(0)

最初的问题陈述是这样的:

给定一个32位无符号整数数组,其中每个数字除了其中三个(恰好只出现一次)之外恰好出现两次,使用O(1)额外空格在O(n)时间内找到这三个数字.输入数组是只读的.如果有k个例外而不是3个怎么办？

如果由于输入限制(阵列最多可以包含2 ³³个条目)而接受非常高的常数因子,则很容易在?(1)时间和?(1)空间上解决这个问题:

for i in lst:
    if sum(1 for j in lst if i == j) == 1:
        print i

因此,为了这个问题,让我们放弃比特长度的限制,并专注于数字可以达到m比特的更普遍的问题.

推广k = 2的算法,我想到的是以下内容:

1. 对具有最低有效位的那些数字1和具有0单独的那些数字进行异或.如果对于两个分区,结果值不为零,我们知道我们已将非重复数字划分为两个组,每个组至少有一个成员
2. 对于每个组,尝试通过检查第二个最低有效位等进一步对其进行分区

不过,有一个特殊情况需要考虑.如果在对一个组进行分区后,其中一个组的XOR值都为零,我们不知道其中一个结果子组是否为空.在这种情况下,我的算法只是将该位丢弃并继续下一个,这是不正确的,例如它输入失败[0,1,2,3,4,5,6].

现在我的想法是不仅要计算元素的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 …