Algorithmus zum Vergleichen eines sortierten Arrays

Question

Ich habe zwei sortierte Arrays. Ich muss herausfinden, ob sie unterschiedlich sind oder nicht.

Diese Arrays enthalten Elemente in einem spezifischen Bereich.

Mehr als ein Element kann unterschiedlich sein.

Arrays können verschiedene Größen haben. In diesem Fall sollte ich in der Lage sein, die Unterschiede aufzuzeigen.

Ein grobes Beispiel:

Eingabe:

array1: 1 2 4 5 8 9 12
array2: 1 4 8 10 12 13 14

Hier liegt der Bereich bei 1-15.

Was ist der optimale Vergleichsalgorithmus?

Ich sollte in der Lage sein, die Unterschiede und Ähnlichkeiten aufzuzeigen, z.B. 4 ist in beiden und 5 fehlt im zweiten Array.

Meine Lösung:

1. Zwei Zeiger, um den Index des Arrays zu verfolgen.

2. Zeige sie auf den Anfang des Arrays.

3. Vergleiche die ersten beiden Elemente.

4. Wenn beide gleich sind --> gehe zum nächsten.
   sonst

   1. Finden Sie das größte der beiden Elemente des Arrays. Sagen wir, array1 hat das größere Element.

   2. Binäre Suche nach dem Element im anderen Array (array2) --> Position dieses Elements in diesem Array sagen pos

   3. Verwerfen Sie die Elemente des Arrays bis zur Position.

5. Inkrementiere die Zeiger. Verwerfen Sie diesen Teil des Arrays bis zu diesen Zeigern. Wiederholen.

Dies hat eine Komplexität von n log n (durchschnittlich viel weniger, dies ist, wenn Sie für jedes Element eine Suche durchführen müssen).

Answer 1

(4.) - anstelle einer binären Suche führen Sie eine lineare Suche durch.

Gesamtkomplexität: O(n) - da Sie jedes Element genau einmal besuchen.

Answer 2

Völlig ungetestet (und funktioniert nicht gut, wenn Duplikate vorhanden sind):

var same = new List();
var inAonly = new List();
var inBonly = new List();

int b = 0;
int a = 0;
//schauen Sie sich zuerst alle Elemente an, bis eine der Listen keine Elemente mehr hat
for(; a < inputa.Count && b < inputb.Count;) {
     //Wenn das Element gleich ist, fügen Sie es zu same hinzu
     //und das Problem mit Duplikaten tritt hier auf, wenn a zwei "1" enthält, aber b nur eine enthält, wird same nur eine "1" anzeigen, aber inAonly wird auch eine "1" enthalten
     if (inputa[a] == inputb[b]){
       same.Add(inputa[a]);
       a++;
       b++;
     }
     //Andernfalls prüfen wir, ob a < b ist. Falls ja, wissen wir, dass a nur in a existiert, ansonsten muss es nur in b existieren.
     else if (inputa[a] < inputb[b])
     {
        inAonly.Add(inputa[a]);
        a++
     } else         {
        inBonly.Add(inputb[b]);
        b++
     }
}
//Fügen Sie den Rest der Elemente hinzu, wenn ein Array länger ist als das andere
for(; a < inputa.Count;a++)
   inAonly.Add(inputa[a]);
for(; b < inputb.Count;b++)
   inBonly.Add(inputb[b]);

Answer 3

Da beide Arrays sortiert sind, ist es am besten, eine lineare Suche zu verwenden.

Answer 4

Wenn die Arrays Blöcke im Speicher waren - etwas, das Sie möglicherweise mit malloc zugewiesen haben, können Sie die Vergleiche beschleunigen, indem Sie das Array in 32- oder 64-Bit-Integer umwandeln. Auf diese Weise können Sie eine Reihe von Array-Elementen mit einem einzigen ==-Test vergleichen.

Außerdem, wenn Sie wissen, dass das Array eine bestimmte Anzahl von Elementen hat, wird das Entrollen der Schleife, zum Beispiel auf 8 If-Anweisungen, schneller sein. Es spart den Vergleich und Sprung am Ende jedes Durchlaufs durch die Schleife.

Answer 5

@Alvin Dein Algorithmus scheint für mich richtig zu sein. Da du Ähnlichkeiten und Unterschiede herausstellen musst, musst du im Falle jedes Unterschieds eine Suche durchführen.

Ich denke, dass die Komplexität besser als nlgn sein wird, da du nicht den kompletten Array bei jedem Unterschied durchsuchen musst. Das liegt daran, dass du die Elemente bis zur Position discarden kannst.