13

2 つの配列が与えられた場合、両方の配列に共通する最大要素を見つける方法は?

両方の配列(n log n)を並べ替えてから、一致するものが見つかるまで、1 つの並べ替えられた配列 (大きい方から始まる) のすべての要素のバイナリ検索を別の配列で実行することを考えていました。

例えば：

a = [1,2,5,4,3]
b = [9,8,3]

Maximum common element in these array is 3

n log n よりもうまくできるでしょうか?

4

6 に答える 6

10

余分なスペースを使用して、1 つの配列でハッシュし、true を返す最大値を追跡しながら、他の配列の各要素を含むことができます。O（n）になります。

于 2012-06-21T15:36:41.410 に答える
7

できますが、O(N)スペースを使用します。
最初の配列を調べて、すべての要素をHashTable. 次に、現在のO(N)
最大値を追跡し、要素が にあるかどうかを確認する 2 番目の配列を調べHashTableます。これもO(N)。したがって、総実行時間はO(N)、O(N)HashTable

Java での例: 

public static int getMaxCommon(int[] a, int[] b){  
  Set<Integer> firstArray = new HashSet<Integer>(Arrays.asList(a));  
  int currentMax = Integer.MIN_VALUE;  
  for(Integer n:b){  
     if(firstArray.contains(n)){  
         if(currentMax < n){  
              currentMax = n  
         }
     }   
  }   
  return currentMax;  
}
于 2012-06-21T15:38:58.230 に答える
3

特定の言語でのさまざまな操作の時間計算量にもよりますが、配列からセットを作成し、2つのセットの共通部分で最大値を見つけるのはどうでしょうか。Pythonでの操作の時間計算量を見ると、平均して、セットの割り当ての場合はO（n）、交差の場合はO（n）、最大値を見つけるためのO（n）になります。したがって、平均的なケースはO（n）になります。

でも！最悪の場合はO（len（a）* len（b））-> O（n ^ 2）になります。これは、集合の交差の最悪の場合の時間計算量のためです。

興味がある場合は、こちらの詳細情報：http ://wiki.python.org/moin/TimeComplexity

于 2012-06-21T15:42:48.460 に答える
1

配列に含まれる数値の範囲が既にわかっている場合は、カウントソートを実行してから、必要に応じてバイナリ検索を実行できます。これにより、O(n) ランタイムが生成されます。

于 2012-06-21T15:43:17.050 に答える
1

擬似コード:

sort list1 in descending order
sort list2 in descending order
item *p1 = list1
item *p2 = list2
while ((*p1 != *p2) && (haven't hit the end of either list))
  if (*p1 > *p2)
    ++p1;
  else
    ++p2;
// here, either we have *p1 == *p2, or we hit the end of one of the lists
if (*p1 == *p2)
  return *p1;
return NOT_FOUND;
于 2012-06-21T15:49:48.950 に答える