arrays - 配列内で繰り返されない要素を1つ見つけますか？

Question

1つの要素だけが繰り返されない要素の配列がありnます。そうでない場合、他のすべての番号は1回以上繰り返されます。また、配列内の数値の範囲に制限はありません。

いくつかの解決策は次のとおりです。

• ハッシュを利用しますが、それは線形の時間計算量になりますが、スペースの複雑さは非常に低くなります
• MergeSortを使用してリストO(nlogn)を並べ替えてから、繰り返されない要素を見つける

より良い解決策はありますか？

Answer 1

一般的なアプローチの 1 つは、バケット化手法 (ハッシュはそのような手法です) を実装して、ID (インデックスなど) を使用して要素を異なる「バケット」に分散し、最小サイズ (この場合は 1) のバケットを見つけることです。この問題は、少数要素問題としても知られていると思います。セット内のユニークな要素と同じ数のバケットがあります。

ハッシュによってこれを行うことは、衝突とアルゴリズムがそれを処理する方法のために問題があります。試行や拡張可能なハッシュなどの特定の連想配列アプローチは、文字列に適しているため、適用されないようです。

上記の 1 つのアプリケーションは、Union-Find データ構造への適用です。あなたのセットはバケットになり、呼び出しごとに $O(\alpha(n))$ のコストで、配列内の各要素に対して MakeSet() と Find() を呼び出す必要があります。ここで、$\alpha(n) $ は非常にゆっくりと成長する逆アッカーマン関数です。これは事実上の定数と考えることができます。

要素が既に存在する場合は、Union を実行する必要があります。最小限のカーディナリティでセットを追跡するためのいくつかの変更により、このソリューションは機能するはずです。この解の時間計算量は $O(n\alpha(n))$ です。

あなたの問題は、要素の一意性の問題にも大まかに関連しているようです。

Answer 2

2 つのアイデアが頭に浮かびます。

• スムーズソートは、メモリ使用量が O(1)、最悪の場合はマージソートとして O( nlogn )、最良の場合は O(n) であることを考えると、引用されたマージソートよりも優れた代替手段になる可能性があります。

• splay treeの (逆の) アイデアに基づいて、葉が使用されると (splay tree のように上向きではなく) 下の方に葉を押すタイプの木を作成できます。これでも同様の O(nlogn) 移植が得られますが、利点は、一意の要素を見つける O(1) ステップであり、それがルートになります。ソート アルゴリズムは O(nlogn) + O(n) の合計であり、このアルゴリズムは O(nlogn) + O(1) になります。

それ以外の場合、あなたが述べたように、ハッシュベースのソリューション（ハッシュ実装セットなど）を使用すると、O（n）アルゴリズム（O（n）がそれへのカウント参照を挿入して追加し、O（n）がセットをトラバースする）になりますユニークな要素を見つけるために）が、理由はわかりませんが、メモリ使用量が気に入らなかったようです。最近はメモリーが安い…

Answer 3

スペースの制限が厳しい場合は、マルチパス スキャンを試してください。

入力に ​​n 個の要素があり、メモリ内に m 個の要素しか保持できないとします。ハッシュ テーブル アプローチを使用する場合、最悪の場合、n/2 の一意の番号を処理する必要があるため、m>n/2 になります。大きな m がない場合は、n 個の要素を k=(max(input)-min(input))/(2m) グループに分割し、n 個の入力要素を k 回 (最悪の場合) スキャンすることができます。場合）：

1 回目の実行: 値が min(input)+m*2 未満の要素のみをハッシュ get/put/mark/whatever します。範囲 (min(input), min(input)+m*2) には最大で m 個の一意の要素があり、それを処理できるためです。運が良ければ、すでにユニークなものを見つけています。それ以外の場合は続行してください。

2 回目の実行: 範囲内の値 (最小 (入力)+m*2、最小 (入力)+m*4) などの要素のみを操作します。

このようにして、時間の複雑さを O(kn) に妥協しますが、O(m) の空間の複雑さの境界を取得します。