Wie finde ich Duplikate in einem Array mit O(n)-Zeit und O(1)-Raum?

Effizienter Algorithmus zum Finden von Duplikaten in O(n)-Zeit und O(1)-Raum

In dieser Programmierherausforderung suchen wir einen effizienten Algorithmus zum Identifizieren und Drucken doppelter Elemente in einem Array von Ganzzahlen im Bereich von 0 bis n-1, mit möglichen Wiederholungen. Die Herausforderung erfordert einen Algorithmus, der innerhalb einer O(n)-Zeitkomplexität arbeitet und nur konstanten Speicherplatz verbraucht.

Ein wirksamer Ansatz für dieses Problem ist die Technik der „Array-Modifikation“. Der Algorithmus funktioniert wie folgt:

1. Erste Schleife:

   • Initialisieren Sie eine Schleife, die jedes Element im Array durchläuft, bezeichnet als A[i].
   • Bestimmen Sie für jedes A[i], ob A[A[i]] gleich A[i] ist.
   • Wenn nicht, tauschen Sie A[i] mit A[ A[i]].

2. Zweite Schleife:

   • Schleife zurücksetzen, um über jedes A[i] zu iterieren noch einmal.
   • Für jedes A[i], das nicht gleich i ist, geben Sie A[i] aus. Dieser Schritt identifiziert die doppelten Elemente, da bei jedem nicht duplizierten Element A[A[i]] gleich i ist (d. h. es befindet sich an der richtigen Position).

Dieser Algorithmus arbeitet in O(n)-Zeiten, da jedes Element in der ersten Schleife höchstens einmal überprüft und geändert wird. Da außerdem keine zusätzlichen Datenstrukturen verwendet werden, wird nur O(1)-Speicherplatz verwendet.

Betrachten Sie beispielsweise das Eingabearray {1, 2, 3, 1, 3, 0, 6}. Nach der Ausführung des Algorithmus wird das Array wie folgt geändert:

[1, 2, 3, 1, 3, 0, 0]

Die zweite Schleife druckt dann die doppelten Elemente 1 und 3.

Das obige ist der detaillierte Inhalt vonWie finde ich Duplikate in einem Array mit O(n)-Zeit und O(1)-Raum?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!