Wie finde ich Duplikate in einem Array mit optimaler zeitlicher und räumlicher Komplexität?

Duplikate mit optimaler zeitlicher und räumlicher Komplexität finden

Einführung:
Die Aufgabe, doppelte Elemente in zu erkennen Ein Array ist ein weit verbreitetes Problem bei der Programmierung. Lösungen, die Hilfsdatenstrukturen wie Hash-Tabellen verwenden, bieten zwar Einfachheit, beeinträchtigen jedoch die Platzeffizienz. In diesem Artikel wird ein genialer Algorithmus vorgestellt, der Duplikate in linearer Zeit O(n) identifiziert und dabei den Speicherplatzverbrauch O(1) konstant hält.

Problemstellung:
Angesichts eines Arrays von n Elementen im Bereich von 0 bis n-1, wobei einige Zahlen mehrmals vorkommen können, finden Sie die doppelten Elemente im Array.

Optimaler Algorithmus:

// Iterate through the array
for i = 0 to n - 1:
    // Swap elements until A[A[i]] = A[i]
    while A[A[i]] != A[i]:
        swap(A[i], A[A[i]])
    end while

// Identify duplicates based on A[i] != i
for i = 0 to n - 1:
    if A[i] != i:
        print A[i]
    end if
end for

Einsicht:
Der Algorithmus nutzt die Tatsache, dass sich jedes Element im Array idealerweise an seinem Index befinden sollte. Es verwendet die Elemente des Arrays, um eine Permutation zu erstellen und sicherzustellen, dass vorhandene Elemente ihren richtigen Indizes zugeordnet werden. Die erste Schleife durchläuft das Array und stellt sicher, dass jedes Element durch Swaps seinen vorgesehenen Index erreicht.

Erklärung:
Die erste Schleife permutiert das Array, sodass für jedes Element x, if Wenn es mindestens einmal vorkommt, befindet sich eine Instanz am Index A[x]. Bei jedem Austausch wird ein Eintrag korrigiert, der einem falschen Element entspricht, wodurch sichergestellt wird, dass die Gesamtzahl der Austauschvorgänge durch die Anzahl der Elemente N-1 begrenzt ist.

Die zweite Schleife identifiziert Duplikate, indem der Index jedes Elements gedruckt wird Element, das nicht mit seinem Index übereinstimmt, was darauf hinweist, dass es im ursprünglichen Array nicht vorhanden ist.

Schlussfolgerung:
Dieser Algorithmus identifiziert effizient doppelte Elemente in einem Array, indem er das Eingabearray geschickt nutzt selbst. Aufgrund seiner O(n)-Zeit- und O(1)-Raumkomplexität eignet es sich für eine Vielzahl praktischer Anwendungen.

Das obige ist der detaillierte Inhalt vonWie finde ich Duplikate in einem Array mit optimaler zeitlicher und räumlicher Komplexität?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!