在列表中找到k个非重复元素，并留出“很少”的空间

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

如果由于输入限制而接受非常高的常数因子，则很容易在Ο(1)时间和Ο(1)空间上解决此问题（该数组最多可包含2 33个条目）：

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

因此，出于这个问题的考虑， 让我们放宽对位长度的限制，将注意力集中在数字最多可以包含@H_326_10@m位的更普遍的问题上。

概括k = 2的算法，我想到的是：

1. 将那些数字的最低有效位1与那些与0单独的那些异或。如果对于两个分区，结果值都不为零，我们知道我们已将非重复数字划分为两组，每组至少有一个成员
2. 对于这些组中的每一个，请尝试通过检查第二低有效位来进一步对其进行划分，依此类推

但是，有一个特殊情况需要考虑。如果在对一个组进行分区之后，其中一个组的XOR值都为零，则我们不知道其中一个子组是否为空。在这种情况下，我的算法只是省去了这一点，而是继续进行下一个，这是不正确的，例如，输入失败[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,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,bits | hibit,X)
    solve(ary,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输入元素的数量在哪里（XORing@H_801_85@ O(m)且最多k分区操作可以成功）和空间复杂度O(m²)（因为@H_326_10@m最大递归深度，而临时数可以是长度@H_326_10@m）。

问题当然是，是否存在一种 正确且 有效的方法，并具有良好的渐近运行时间（为了完整性起见，请假设此处k << n和@H_326_10@m << n此处），这也需要很少的额外空间（例如，将输入分类的方法将不被接受，因为我们O(n)不能修改输入内容，所以至少需要额外的空间！）。

编辑：@H_801_85@ 既然上面的算法被证明是不正确的，那么很高兴看到它如何变得正确，也许可以通过降低效率来解决。空间复杂度应为o(n*m)（即输入位数总数为次线性）。k如果这样可以使任务更容易，则可以将其作为附加输入。