配列内の複製要素の検索

Question

サイズnの配列があり、配列に含まれる要素は1とn-1の間にあり、各要素が1回発生し、1つの要素が複数回出現する。この要素を見つける必要があります。

これは非常によくある質問ですが、まだ適切な答えが見つかりませんでした。ほとんどの提案は、私は配列のすべての要素を追加し、それからすべてのインデックスの合計を引く必要がありますが、要素の数が非常に多い場合、これは機能しません。オーバーフローします。 XORゲートdup = dup^arr[i]^iの使用に関する提案もありますが、これは私には分かりません。

私はこのアルゴリズムを思いつきました。これは加算アルゴリズムの強化であり、オーバーフローの可能性を大幅に低減します！

for i=0 to n-1 
    begin : 
    diff = A[i] - i; 
    sum = sum + diff; 
    end 

diff重複した要素が含まれていますが、この方法を使用して、私は、重複する要素のインデックスを見つけることができません。そのためには、アレイをもう一度トラバースする必要があります。これは望ましくありません。誰かが追加メソッドやXORメソッドが含まれていない、より良い解決策を考え出すことができますか？

Answer 1

問題の説明の制約によっては、この問題を考える方法はたくさんあります。

正確に1つの要素が重複していることがわかっている場合は、この問題を解決する方法はたくさんあります。特に巧妙なソリューションの1つは、ビット単位のXOR演算子を使用することです。

1. XORがそれほど（x^y）は、連想である^ Z = X ^（Y^Z）
2. XORが可換である：X^Y = Y^X
3. XORは、以下の興味深い特性を有していますXORは、独自の逆である：X^Y = 0 IFF X = Y
4. XORは、IDとしてゼロを有する：ここで、X^0 = X

プロパティ（1）及び（2）は、撮影時ことを意味しますグループの値の排他的論理和では、要素に排他的論理和を適用する順序は関係ありません。要素を並べ替えるか、適切にグループ化することができます。プロパティ（3）は、同じ値を複数回XORした場合にゼロを返し、プロパティ（4）はXORが0の場合は元の数に戻ることを意味します。これらのプロパティをすべてまとめてみると、興味深い結果が得られます。つまり、グループのXORを取ると、その結果はグループ内のすべての数字の奇数回のXORになります。その理由は、偶数回に出現する数字を一緒にXORすると、その数字のXORをペアの組に分解することができるからです。各対は（3）により0に排他的論理和をとり、これらのすべてのゼロの排他的論理和をとると、（4）によってゼロが戻される。その結果、すべての偶数多重度が相殺される。

これを使用して元の問題を解決するには、次の手順を実行します。まず、リスト内のすべての数字をXORします。これは、奇数回に現れるすべての数の排他的論理和（XOR）を与え、最終的に複写を除いて1から（n-1）までのすべての数となる。さて、この値を1から（n-1）までのすべての数のXORでXORします。これにより、以前にキャンセルされなかった範囲1から（n-1）までのすべての数値が相殺され、重複した値だけが残されます。さらに、これはO（n）時間で実行され、すべての値の排他的論理和が単一の整数に収まるため、O（1）空間のみを使用します。

元の投稿では、1からn-1までの整数の合計がn（n-1）/ 2であるという事実を利用して動作する代替アプローチを考えました。しかし、これが整数オーバーフローを引き起こし、問題を引き起こすことに懸念がありました。ほとんどのマシンでは、オーバーフローが発生することは間違いありませんが、（ほとんどのマシンでは）これは問題ではありません。なぜなら、算術演算は固定精度の整数、通常は32ビットの整数を使用して行われるからです。整数のオーバーフローが発生した場合、結果の数値は無意味ではありません。むしろ、実際の結果を計算した後に、最も低い32ビットを除いてすべてを落とした場合に得られる価値です。数学的に言えば、これはモジュラ演算と呼ばれ、コンピュータの演算は2 のモジュロで行われます。より一般的には、整数がある固定kに対してモジュロkで格納されているとします。

幸いにも、あなたが知っていて正常な算術から愛している算数法則の多くは、依然としてモジュラー算術で保持されています。私たちは専門用語で正確にするだけです。 xとyがkで割ったときに同じ剰余を残すならば、xはyを法とするk（x ≡ _kと表される）と一致すると言う。ほとんどのハードウェアで整数のオーバーフローが発生した場合、その結果の値は真の値のモジュロkと一致し、kはワードサイズに依存するため、物理マシンで作業する場合は重要です。幸いなことに、以下の法律は剰余演算に当てはまる：

例えば：

1. Y X ≡ _K場合と≡ _K Zは、X + ≡ _KワットY + Z wは次いで
2. Y _K ≡ X場合と≡ _K Z W、XW ≡ _k yz。

これは、配列の要素の総和を求め、期待される合計を引いて重複値を計算する場合、整数のオーバーフローがあってもすべてが正常に機能することを意味しますハードウェアで同じ値（モジュロk）を生成します。つまり、オーバーフローを全く考慮する必要のないXORベースのアプローチを使用することもできます。 :-)

正確に1つの要素が重複することは保証されていませんが、要素の配列を変更することができる場合は、に重複した値を見つけるための美しいアルゴリズムがあります。 This earlier SO questionはこれを達成する方法を説明している。直感的には、bucket sortを使用してシーケンスを並べ替えることができます。要素の配列自体がリサイクルされ、バケットのスペースも保持されます。

正確に1つの要素が複製されていることが保証されておらず、要素の配列を変更できない場合は、の問題ははるかに困難です。これは伝えられるところによれば、Don Knuthを解決するのに24時間かかった古典的な（そして難しい）インタビューの問題です。そのトリックは、配列を数字1-nから1-（n-1）に関数として扱い、その関数への2つの入力を探して、問題をcycle-findingのインスタンスに減らすことです。しかし、得られたアルゴリズムは​​と呼ばれ、非常に美しく簡単です。興味深いことに、線形の時間と一定の空間でリンクリストのサイクルを検出するのと同じアルゴリズムです。それは定期的にソフトウェアのインタビューで出てくるので、私はそれを見てお勧めします。

解析、正当性証明、およびPython実装のアルゴリズムの詳細については、this implementationを参照してください。

希望すると便利です。

Answer 2

要素を追加すると、要素の合計と予想される合計を計算する際に、中間集計のmod（％）を取るだけで済みます。 mod演算では、2nのようなものを使うことができます。また、差し引き後に値を修正する必要があります。