Vergleichen Sie zwei Arrays und erstellen Sie ein neues Array mit gleichen Elementen in C

Question

Das Problem besteht darin, zwei Arrays für den gleichen Integer-Wert zu überprüfen und passende Werte in ein neues Array zu setzen.

Lassen Sie sagen, ich zwei Arrays haben

a[n] = {2,5,2,7,8,4,2}
b[m] = {1,2,6,2,7,9,4,2,5,7,3}

Jedes Array eine andere Größe sein kann.

Ich muss überprüfen, ob die Arrays übereinstimmende Elemente haben und sie in ein neues Array legen. Das Ergebnis sollte in diesem Fall sein:

array[] = {2,2,2,5,7,4}

Und ich brauche, es zu tun in O (n.log (n) + m.log (m)).

Ich weiß, es gibt eine Möglichkeit, mit Merge Sortierung oder setzen Sie eine der Array in einem Hash-Array, aber ich weiß wirklich nicht, wie Sie es implementieren.

Ich werde wirklich Ihre Hilfe zu schätzen wissen, danke !!!

Answer 1

Wie Sie bereits herausgefunden haben Sie Mergesort verwenden können (implementierende es sprengt den Rahmen dieser Antwort ist, nehme ich an Sie, eine Lösung auf wikipedia oder die Suche auf Stack-Überlauf finden), so dass Sie nlogn + mlogm Komplexität n Annahme bekommen ist die Größe des ersten Arrays und m ist die Größe eines anderen.

Lassen Sie sich das erste Array nennen a (mit der Größe n) und dem zweiten b (mit der Größe m). Sortieren Sie zuerst diese Arrays (merge sort würde uns nlogn + mlogm Komplexität geben). Und jetzt haben wir:

a[n] // {2,2,2,4,5,7,8} und b[n] // {1,2,2,2,3,4,5,6,7,7,9}

n <= m Angenommen wir können einfach iterieren Simultane Vergleich coresponding Werte:

Aber läßt erste Array zuweisen int c[n]; Ergebnisse zu speichern (Sie auf der Konsole drucken können anstelle des Speicherns wenn Sie brauchen). Und nun die Schleife selbst:

int k = 0; // store the new size of c array! 
for (int i = 0, j = 0; i < n && j < m;) 
{ 
    if (a[i] == b[j]) 
    { 
     // match found, store it 
     c[k] = a[i]; 
     ++i; ++j; ++k; 
    } 
    else if (a[i] > b[j]) 
    { 
     // current value in a is leading, go to next in b 
     ++j; 
    } 
    else 
    { 
     // the last possibility is a[i] < b[j] - b is leading 
     ++i; 
    } 
} 

Hinweis: die Schleife selbst ist n+m Komplexität im schlimmsten Fall (nicht vergessen n <= m Annahme), die geringer ist als für so overal Komplexität Sortierung nlogn + mlogm ist. Jetzt können Sie c Array iterieren (es ist Größe ist eigentlich n wie wir zugeordnet, aber die Anzahl der Elemente darin ist k) und tun, was Sie mit diesen Zahlen brauchen.

Answer 2

Von der Art, wie Sie es erklären, wäre dies die Schleife über das kürzere Array und überprüfen Sie es gegen das längere Array. Nehmen wir an, dass A das kürzere Array und B das längere Array ist. Erstellen Sie ein Ergebnis-Array C.

1. Schleife über jedes Element in A, nennt I

2. Wenn I in B gefunden wird, entfernt sie aus B und es in C, bricht aus der Testschleife.

3. Gehen Sie jetzt auf das nächste Element in A.

Das bedeutet, dass, wenn eine Zahl, die ich zweimal in A gefunden wird, und dreimal in B, dann werde ich nur, wenn Sie zweimal in C angezeigt beenden, dann erscheint jede in beiden Arrays gefundene Zahl in C so oft wie sie tatsächlich in beiden erscheint.

Ich setze sorgfältig keinen vorgeschlagenen Code ein, da es sich bei Ihrer Frage um eine Methode handelt, die Sie verwenden können. Sie sollten den Code selbst herausfinden.

Answer 3

Ich würde geneigt sein, den folgenden Ansatz:

1) Sortieren Array B. Es gibt diese viele gut veröffentlicht Sortieralgorithmen zu tun, sowie mehr Implementierungen in verschiedenen allgemein verwendeten Bibliotheken.

2) Schleife durch Array A und für jedes Element eine binäre Suche (oder einen anderen geeigneten Algorithmus) auf Array B für eine Übereinstimmung. Wenn eine Übereinstimmung gefunden wird, entfernen Sie das Element aus Array B (um zukünftige Übereinstimmungen zu vermeiden) und fügen Sie es zum Ausgabe-Array hinzu.