Finden Sie das maximale Element, das in zwei Arrays gemeinsam ist?

Question

Bei zwei Arrays, wie findet man das maximale Element, das beiden Arrays gemeinsam ist?

Ich dachte daran, beide Arrays (n log n) zu sortieren und dann die binäre Suche jedes Elements von einem sortierten Array (beginnend mit einem größeren) in einem anderen Array durchzuführen, bis eine Übereinstimmung gefunden wurde.

zB:

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

Maximum common element in these array is 3 

Können wir es besser machen als n log n?

Answer 1

Mit etwas mehr Speicherplatz können Sie in einem Array hash, dann ein contains auf jedes Element des anderen Array verfolgen den größten Wert, der wahr zurückgibt. Wäre O (n).

Answer 2

Sie können aber O(N) Platz verwenden.
Gehen Sie einfach durch das erste Array und legen Sie alle Elemente in eine HashTable. Dies ist O(N)
Dann gehen Sie durch das zweite Array verfolgen das aktuelle Maximum und überprüfen, ob das Element in der HashTable ist. Dies ist auch O(N). So Gesamtlaufzeit ist O(N) und O(N) zusätzlicher Platz für das HashTable

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

Answer 3

Während es auf der Zeit Komplexität der verschiedenen Operationen in bestimmten Sprachen abhängt, wie etwa Sets von den Anordnungen zu schaffen und den maximalen Wert im Schnittpunkt der beiden Mengen finden? Geht man von der Komplexität der Operationen in Python aus, wären im Durchschnitt O (n) für die Mengenzuweisungen, O (n) für die Schnittpunkte und O (n) für das Finden des Maximalwerts. Der durchschnittliche Fall wäre also O (n).

Jedoch! Der schlechteste Fall wäre O (len (a) * len (b)) -> O (n^2), wegen der ungünstigsten Zeitkomplexität der gesetzten Schnittpunkte.

Mehr Infos hier, wenn Sie interessiert sind: http://wiki.python.org/moin/TimeComplexity

Answer 4

Wenn Sie bereits den Bereich von Zahlen kennen, die in Ihrer Arrays wäre, könnten Sie führen Art zu zählen, und dann die binäre Suche durchführen, wie Sie wollten. Dies würde O (n) Laufzeit ergeben.

Answer 5

Pseudocode:

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

keine perfekt, aber eine einfache Lösung, O (len (array1) + len (array2))

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