元の問題ステートメントは次のとおりです。
32ビットの符号なし整数の配列で、3つ（1つだけ）を除いてすべての数値が正確に2回現れる場合、O（1）の余分なスペースを使用してO（n）時間でこれらの3つの数値を見つけます。入力配列は読み取り専用です。3ではなくkの例外がある場合はどうなりますか？
入力制限のために非常に高い定数係数を受け入れる場合、これをΟ(1)時間と空間で簡単に解決できます（配列には最大2つの33エントリを含めることができます）。Ο(1)
for i in lst:
if sum(1 for j in lst if i == j) == 1:
print i
したがって、この質問のために、ビット長の制限を解除し、数値が最大ビットになる可能性があるより一般的な問題に集中しましょうm。
k = 2のアルゴリズムを一般化すると、私が念頭に置いていたのは次のとおりです。
- これらの数値の最下位ビット
1と0個別の数値をXORします。両方のパーティションで、結果の値がゼロでない場合、繰り返されない数値を2つのグループに分割し、それぞれに少なくとも1つのメンバーが含まれていることがわかります。 - これらのグループごとに、2番目に最下位ビットなどを調べてさらに分割してみてください。
ただし、考慮すべき特別な場合があります。グループを分割した後、グループの1つのXOR値が両方ともゼロである場合、結果のサブグループの1つが空であるかどうかはわかりません。この場合、私のアルゴリズムはこのビットを省略して次のビットを続行しますが、これは正しくありません。たとえば、入力に対して失敗します[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入力要素の数（XORはO(m)、最大でk分割操作が成功する可能性があります）とスペースの複雑さO(m²)（m最大の再帰深度であり、一時的な数は次のようになる可能性があるため）です。長さm）。
問題はもちろん、適切で効率的なアプローチがあり、漸近的なランタイムが良好であるかどうかです（完全を期すためにk << n、m << nここでは、追加のスペースもほとんど必要ありません（たとえば、入力を並べ替えるアプローチは受け入れられません）。O(n)入力を変更できないため、少なくとも追加のスペースが必要になるためです！）。
編集：上記のアルゴリズムが正しくないことが証明されたので、もちろん、おそらく少し効率を下げることによって、どのように正しくすることができるかを確認するのは良いことです。スペースの複雑さはにある必要がありますo(n*m)（つまり、入力ビットの総数が劣線形です）。kタスクが簡単になる場合は、追加の入力として使用してもかまいません。