2つの配列で共通する最大要素を探しますか？

Question

2つの配列がある場合、両方の配列に共通の最大要素を見つける方法は？

私は、両方の配列（n log n）をソートして、マッチが見つかるまで別の配列の1つのソート済み配列（より大きなものから順に）のすべての要素をバイナリ検索することを考えていました。

例：

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

Maximum common element in these array is 3 

我々は、n個のログnよりも優れて行うことができますか？

Answer 1

余分なスペースを置いて1つの配列にハッシュすると、他の配列の各要素にcontainsを実行してtrueを返す最大値を記録します。 O（n）になりますか？

Answer 2

O(N)スペースを使用することができます。
最初の配列を通り、すべての要素をHashTableに配置してください。これはO(N)
現在の最大値を追跡し、要素がHashTableにあるかどうかを確認しながら2番目の配列を調べます。これもO(N)です。それは、特定の言語で様々な操作の時間の複雑さに依存するが、どのように配列からセットを作成する方法について

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; 
} 

Answer 3

： だから、合計ランタイムはO(N)とJavaでHashTable

例についてO(N)余分なスペースです2つのセットの交点の最大値を見つけることはできますか？ Pythonでの操作の時間複雑度は、設定された代入ではO（n）、交差点ではO（n）、最大値を見つけるにはO（n）が平均です。だから、平均的な場合はO（n）になります。

ただし、最悪のケースは、集合交点の最悪のケースの複雑さのために、O（len（a）* len（b）） - > O（n^2）である。もし興味があるなら、ここ

詳細情報：http://wiki.python.org/moin/TimeComplexity

Answer 4

あなたはすでにあなたの配列になります番号の範囲を知っている場合、あなたはソートを数え行うことができ、その後、あなたが望んでいたように、バイナリ検索を実行します。これにより、O（n）ランタイムが生成されます。

Answer 5

擬似コード：

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; 

Answer 6

完璧ではないが、シンプルなソリューション、O（LEN（配列1）+ LEN（配列2））

import sys 


def find_max_in_common(array1, array2): 
    array1 = set(array1) 
    array2 = set(array2) 

    item_lookup = {} 

    for item in array1: 
     item_lookup[item] = True 

    max_item = -sys.maxsize 

    intersection = False 

    for item in array2: 
     if not item_lookup.get(item, None): 
      continue 
     else: 
      intersection = True 
      if item > max_item: 
       max_item = item 

    return None if not intersection else max_item