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

Wenn array1 und array2 die gleiche Größe haben, dann iteriere über sie und vergleiche sie Element für Element. Wenn der erste Unterschied gefunden wird => die Arrays sind unterschiedlich. Wenn du das Ende der Arrays erreichst, bedeutet das, dass sie gleich sind. Die Komplexität beträgt O(Arraylänge) in der Zeit und O(1) im Speicher.

Wenn array1 und array2 unterschiedliche Größe haben, dann allokiere ein weiteres Array mit der Größe - dem Bereich der Elemente und initialisiere es mit Nullen (Array3). Für jedes Element in array1 erhöhe das Element in Array3 wie folgt: Array3[array1[i]]++

Danach iteriere auf die gleiche Weise über Array2, aber verringere: Array3[array2[i]]--

Danach hast du für jedes Element in Array3 3 Möglichkeiten:

• wenn Array3[i] == 1 //dann ist Element i in Array1, aber nicht in Array2
• wenn Array3[i] == -1 //dann ist Element i in Array2, aber nicht in Array1
• wenn Array3[i] ==0 //dann ist Element i in beiden Arrays oder in keinem von ihnen.

Zeitkomplexität - O(Bereich), Speicherkomplexität - O(Bereich). Wenn der Bereich nicht bei 0 beginnt, kannst du für jeden Index eine Verschiebung vornehmen.

Beispiel:

• Bereich: 1-15
• Array1: 1 2 4 5 8 9 12
• Array2: 1 4 8 10 12 13 14

Nach Schritt1 wird Array3 so aussehen:

Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Wert: 1 1 0 1 1 0 0 1 1  0  0  1  0  0  0

Nach Schritt2 wird Array3 so aussehen:

Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Wert: 0 1 0 0 1 0 0 0 1 -1  0  0 -1 -1  0

Answer 2

Sie sind auf dem richtigen Weg, wie Sie das angehen, jedoch ist die Suche nicht notwendig. (siehe unten für tatsächlichen Algorithmus)

Beginnen Sie mit 2 Zeigern, die auf den Anfang zeigen:

        v
array1: 1 2 4 5 8 9 12

        v
array2: 1 4 8 10 12 13 14

(genau wie Sie) Wenn die Elemente gleich sind, fügen Sie sie Ihrem "In-Both"-Set hinzu und inkrementieren Sie beide Zeiger, sodass wir nun haben:

          v
array1: 1 2 4 5 8 9 12

          v
array2: 1 4 8 10 12 13 14

Wenn wir jetzt auf unterschiedliche Elemente stoßen, anstatt hier zu suchen, können wir davon profitieren, dass wir genau wissen, dass es kein 2 gibt, nachdem der Zeiger in array2 steht. Daher fügen wir 2 unserem "Nur_in_array1"-Set hinzu und inkrementieren nur den array1-Zeiger. So bekommen wir:

            v
array1: 1 2 4 5 8 9 12

          v
array2: 1 4 8 10 12 13 14

Wir treffen auf Übereinstimmungen, also fügen wir 4 zum "In-Both" hinzu und inkrementieren beide Zeiger:

              v
array1: 1 2 4 5 8 9 12

            v
array2: 1 4 8 10 12 13 14

Wenn Sie dieses Muster fortsetzen, werden Sie schließlich auf folgendes stoßen:

                     v
array1: 1 2 4 5 8 9 12

                  v
array2: 1 4 8 10 12 13 14

und wenn der erste Zeiger das Array verlässt, wissen Sie, dass die restlichen Elemente im zweiten (längeren) Array nicht im ersten enthalten sind.

Um den Algorithmus zu verallgemeinern:

• Starten Sie mit 2 Zeigern am Anfang beider Arrays (und initialisieren Sie alle Datenstrukturen, in denen Sie Informationen speichern möchten: Ich habe 3 Listen/Sets verwendet)

• Jetzt können drei Fälle auftreten

  1. Wert von p1 ist gleich p2: Fügen Sie den Wert Ihrem in beiden-Array hinzu und inkrementieren Sie beide

  2. Wert von p1 ist kleiner als p2: Fügen Sie den Wert von p1 Ihrem nur in array1-Array hinzu und inkrementieren Sie nur p1

  3. Wert von p1 ist größer als p2: Fügen Sie den Wert von p2 Ihrem nur in array2-Array hinzu und inkrementieren Sie nur p2

• Loop über diese Bedingungen, bis Sie das Ende eines (oder beider, wenn es so passiert) Ihrer Arrays erreichen. Fügen Sie dann die verbleibenden Elemente in der anderen Liste zu ihrer jeweiligen nur in arrayX-Liste hinzu.

Dieser Algorithmus greift jedes Element nur einmal ab, daher sollte er O(n) sein. Hoffe, das hilft