配列内の共通の重複を見つける

配列の要素の範囲に関する情報を持たない2つの整数配列があります。私が知っているのは、2つの配列mとnの長さです。今度は両方の配列にいくつかの重複があります。私は両方の配列から最低の共通複製を探したい。私はメモリが限られていると仮定し、これをどのように解決するのですか？配列内の共通の重複を見つける

出典

2011-08-04 user754740

MergeSortアルゴリズムがこの問題を解決するのに役立つ場合があります。 MergeSortアルゴリズムは、基本的にリスト内の要素をソートするためのものですが、その主要な要点は、Divide and Conquer Approachです。あなたは記憶が限られていると述べているので、Divide and Conquerは問題を解決するための合理的なアプローチのようです。

出典

2011-08-04 15:57:30

マージソート、マージ手順にソートするために余分なスペースを必要と答えている交差点で最も低いキーを、見つけます。したがって、この問題では、元の配列をソートするために2つの中間配列が必要になります。しかし、ソート後も、どのようにして両方の配列から共通の複製を識別できますか？それ以上のバッファを消費することなく処理できますか？ – user754740

あなたが言ったことはソートの文脈で真ですが、言及したように、重複を探していて、配列1の特定の要素が配列2に存在するかどうかをチェックするだけです。したがって、もっとバッファを必要としないと思います。 –

配列が最初にソートされていないことを明確にしたいと思います。配列をソートするとarray1の要素をチェックしてarray2にあると言っていますか？ – user754740

1つの可能な方法（これはおそらくメモリとパフォーマンスの両方を行うより効率的な方法です）。

第1および第2の配列に対して2つのmapインスタンスAおよびBを作成します。 keyは整数であり、valueはそれぞれの配列の整数です。
値がAとBの両方に2未満
の両方Aのキーセットを取るある(key,value)ペアを削除
従って両方の配列内の各整数の出現回数をカウントし、マップAに格納し、B Bと交差点を見つける。

出典

2011-08-04 16:05:38 Timo

私はステップを理解しましたが、静的ハッシュテーブルがあれば、キーと値のペアをどのように削除しますか？ハッシュテーブルから削除するときに発生するパフォーマンス上の問題はどれくらいのものがあるのでしょうか？または、この問題が動的ハッシュテーブルに依存することを意味しますか？ – user754740

削除ステップの代わりに、実際にはハッシュテーブルをたどってキーを値2以上のセットに集めてハッシュテーブル全体を破棄することができます。 – Timo

配列内の共通の重複を見つける

答えて

関連する問題