0

今日の初めに、2つの配列に共通する最大要素を見つけるために同様の問題を尋ねました。ここでいくつかの良い解決策があります（2つの配列に共通する最大の要素を見つけますか？）。

2つの配列の代わりに、n個の異なる配列に共通する最大の要素を見つけなければならない場合はどうでしょうか。

例：

 array1 = [1,5,2,4,6,88,34]
 array2 = [1,5,6,2,34]
 array3 = [1,34]
 array4 = [7,99,34]

Here the maximum element which is common in all the arrays is 34.

array1、array2 ..... array（N-1）のハッシュマップを個別に作成してから、これらの各ハッシュマップのarrayNのすべての要素をチェックして、最大要素（すべてのハッシュマップに存在する場合）を追跡することをお勧めします。 ）？

これよりも優れたソリューションはありますか？

4

2 に答える 2

1 
For each array A_n:
  Add all elements in A_n to a hashset, H_n

Create a hashmap, M, which maps values to counts.
For each hashset H_n:
  For each value, v, in H_n:
    M[v]++

Go through M for the highest value with count == N

これは、O（n）の時間と空間で実行されます。ここで、nはすべての配列の要素の総数です。また、単一の配列に複製されている要素を適切に処理します。これについては言及していませんが、一部のアルゴリズムで問題が発生する可能性があります。単一の配列に重複する要素がないことがわかっている場合は、最初の手順をスキップして、配列から直接Mに値を追加できます。

于 2012-06-21T20:25:22.987 に答える
0

ハッシュマップは、最大要素を追跡するのに適していません。必要なのは、最大ヒープまたはハッシュセットです。

n個の最大ヒープを作成し、それらのn個をトラバースします。共通のmax要素を取ります。これは実装が難しいかもしれません。

別のアプローチは、すべてのセットの交点を見つけて、交点から最大値を取得することです。この場合、ハッシュセットを使用できます。

于 2012-06-21T17:46:27.997 に答える