Finden gemeinsamer Elemente in zwei Arrays unterschiedlicher Größe

Ich habe ein Problem, gemeinsame Elemente in zwei Arrays zu finden, und das ist von unterschiedlicher Größe.

Nimm , Array A1 von Größe n und Array A2 von Größe mund m != n

Bisher habe ich versucht, Listen einzeln zu durchlaufen und Elemente in eine andere Liste zu kopieren. Wenn das Element bereits enthält, markieren Sie es, aber ich weiß, dass es keine gute Lösung ist.

Sortieren Sie die Arrays. Iterieren Sie sie dann mit zwei Zeigern, wobei Sie immer denjenigen vorrücken, der auf den kleineren Wert zeigt. Wenn sie auf gleiche Werte zeigen, haben Sie einen gemeinsamen Wert. Dies ist O(n log n+m log m), wobei n und m die Größen der beiden Listen sind. Es ist wie ein Zusammenführen Zusammenführen, sortierenaber wo Sie nur eine Ausgabe erzeugen, wenn die Werte, auf die gezeigt wird, gleich sind.

def common_elements(a, b):
  a.sort()
  b.sort()
  i, j = 0, 0
  common = []
  while i < len(a) and j < len(b):
    if a[i] == b[j]:
      common.append(a[i])
      i += 1
      j += 1
    elif a[i] < b[j]:
      i += 1
    else:
      j += 1
  return common

print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

Ausgänge

Common values: 1, 4

Wenn die Elemente nicht vergleichbar sind, werfen Sie die Elemente aus einer Liste in eine Hashmap und vergleichen Sie die Elemente in der zweiten Liste mit der Hashmap.

Wenn Sie es effizient machen möchten, würde ich das kleinere Array in ein Hashset konvertieren und dann das größere Array iterieren und prüfen, ob das aktuelle Element im Hashset enthalten war. Die Hash-Funktion ist im Vergleich zum Sortieren von Arrays effizient. Das Sortieren von Arrays ist teuer.

Hier ist mein Beispielcode

import java.util.*;
public class CountTest {     
    public static void main(String... args) {        
        Integer[] array1 = {9, 4, 6, 2, 10, 10};
        Integer[] array2 = {14, 3, 6, 9, 10, 15, 17, 9};                    
        Set hashSet = new HashSet(Arrays.asList(array1)); 
        Set commonElements = new HashSet();        
        for (int i = 0; i < array2.length; i++) {
            if (hashSet.contains(array2[i])) {
                commonElements.add(array2[i]);
            }
        }
        System.out.println("Common elements " + commonElements);
    }    
}

Ausgabe:

Gemeinsame Elemente [6, 9, 10]

Bei APL:

∪A1∩A2

Beispiel:

      A1←9, 4, 6, 2, 10, 10
      A1
9 4 6 2 10 10

      A2←14, 3, 6, 9, 10, 15, 17, 9
      A2
14 3 6 9 10 15 17 9

      A1∩A2
9 6 10 10
      ∪A1∩A2
9 6 10 

Wirf dein A2-Array in ein HashSet und iteriere dann durch A1; wenn das aktuelle Element in der Menge ist, ist es ein gemeinsames Element. Dies benötigt O(m + n) Zeit und O(min(m, n)) Platz.

Sieht aus wie verschachtelte Schleifen:

commons = empty
for each element a1 in A1
   for each element a2 in A2
      if a1 == a2
         commons.add(a1)

Sollte überhaupt keine Rolle spielen, wenn die Arrays die gleiche Größe haben.

Abhängig von der verwendeten Sprache und dem verwendeten Framework können Set-Operationen nützlich sein.

Versuchen häufen beide Arrays, gefolgt von einer Zusammenführung, um den Schnittpunkt zu finden.

Java-Beispiel:

public static <E extends Comparable<E>>List<E> intersection(Collection<E> c1,
                                                            Collection<E> c2) {
    List<E> result = new ArrayList<E>();
    PriorityQueue<E> q1 = new PriorityQueue<E>(c1),
                     q2 = new PriorityQueue<E>(c2);
    while (! (q1.isEmpty() || q2.isEmpty())) {
        E e1 = q1.peek(), e2 = q2.peek();
        int c = e1.compareTo(e2);
        if (c == 0) result.add(e1);
        if (c <= 0) q1.remove();
        if (c >= 0) q2.remove();
    }
    return result;
}

Weitere Beispiele für das Zusammenführen finden Sie in dieser Frage.

Die Komplexität dessen, was ich gebe, ist O(N*M + N).

Beachten Sie auch, dass dies der Fall ist Pseudocode C Und dass es eindeutige Werte liefert.

z.B.[1,1,1,2,2,4] und [1,1,1,2,2,2,5] Wird zurückkehren [1,2]

Die Komplexität ist
N*M Ursache der for Schleifen

+ N Ursache der Überprüfung, ob es bereits in der vorhanden ist ArrayCommon[] (welches ist n Größe für den Fall Array2[] enthält Daten, die einen Teil der duplizieren Array1[] Angenommen, N ist die Größe des kleineren Arrays (N < M).

int Array1[m] = { Whatever };
int Array2[n] = { Whatever };
int ArrayCommon[n] = { };

void AddToCommon(int data)
{
    //How many commons we got so far?
    static int pos = 0; 
    bool found = false;
    for(int i = 0 ; i <= pos ; i++)
    {
        //Already found it?
        if(ArrayCommon[i] == data)
        {
            found = true;
        }
    }
    if(!found)
    {
        //Add it
        ArrayCommon[pos] = data;
        pos++;
    }
}

for(int i = 0 ; i < m ; i++)
{
    for(int j = 0 ; j < n ; j++)
    {
        //Found a Common Element!
        if(Array1[i] == Array2[j])
            AddToCommon(Array1[i]);
    }
}