次の問題に遭遇しました：
「奇数回出現する配列内のすべての要素を見つける」。
これについての私の考えは次のとおりです。
使用HashMap: HashMap のキーとして配列に値を追加します。各キーに対応する値は、そのキーに遭遇した回数です。
O(N log N) のクイック ソートを使用して配列をソートし、配列をトラバースして、どの要素が奇数回発生するかを確認します。
これに対する他のアプローチはありますか？いいえの場合、これら 2 つのアプローチのどちらが優れていますか?
前もって感謝します！
「より良い」は文脈によって異なります。ハッシュ マップまたはハッシュ セットを使用すると高速になり、元の配列を変更しないという利点がありますが、O(N) の余分なメモリが必要になります。並べ替えとカウントには時間がかかり、配列が変更されますが、余分なメモリは必要ありません。
どちらのソリューションを選択するかは、追加のメモリを確保できるかどうかによって異なります。
基本的に、これは効率を再調整する練習として行うことができます: 数字のリストを調べ、セットに既にある数字ごとに、それをもう一度削除します。そうすれば、比較セットは可能な最大サイズの約半分になります。もちろん、それは O(n lg n) を変更せず、各ステップで割り当て/割り当て解除を取得しますが、これはおそらくかなり高価です。
したがって、混合戦略を使用するのは興味深いかもしれません: クイックソートはかなり高速ですが、基本的には、2 つのエントリが等しい場合はいつでも合体させ、少なくとも (n-1)/2 エントリが等しい場合に使用します。クイックソートは、ソート中の要素の削除に実際には対応していません。
したがって、配列ベースのアプローチ (割り当てコストを削減するため) では、ヒープベースのアプローチを使用したいと思います。等しい要素に遭遇するたびに、1つ削除します。ヒープソートはクイックソートとかなり競争力があり、事前にツリーを剪定できることは役に立ちます。