Wie kann man Duplikate in einem Array von Zahlen von 0 bis n-1 in O(n)-Zeit und O(1)-Raum finden?

Duplikate in O(n)-Zeit und O(1)-Raum finden

Gegeben sei ein Array mit n Elementen, das Zahlen von 0 bis n enthält -1, wo einige Zahlen möglicherweise mehrmals vorkommen, besteht das Ziel darin, die doppelten Elemente in O(n)-Zeit zu finden und konstanten Speicherplatz zu verwenden.

Um dies zu erreichen, können wir einen faszinierenden Ansatz verwenden, der nicht Es sind keine zusätzlichen Datenstrukturen wie Hash-Tabellen erforderlich.

Der vorgeschlagene Algorithmus funktioniert wie folgt:

1. Permutationsschleife:

   • Durchlaufen Sie das Array für i von 0 bis n-1.
   • Führen Sie innerhalb dieser Schleife die folgenden Schritte aus, bis A[A[i]] gleich A[i] ist. Dies impliziert, dass sich das Element A[i] an der richtigen Position befindet.
   • Vertauschen Sie A[i] mit A[A[i]]. Dadurch wird das Element A[i] effektiv einen Schritt näher an seine korrekte Position gebracht.

2. Duplikationsidentifikationsschleife:

   • Durchlaufen Sie das Array noch einmal, von i von 0 bis n-1.
   • Wenn A[i] nicht gleich i ist, bedeutet dies, dass es am Index A[i] ein Duplikat von i gibt.
   • A[i] als Duplikat drucken.

Dieser Algorithmus stellt sicher, dass alle doppelten Elemente identifiziert werden. Die äußere Schleife wird n-mal ausgeführt, während die innere Schleife höchstens n-1-mal ausgeführt wird. Daher läuft der Algorithmus in O(n)-Zeit. Es verwendet keine zusätzlichen Datenstrukturen, was bedeutet, dass es im O(1)-Raum arbeitet.

Der bereitgestellte Code veranschaulicht die Implementierung des Algorithmus in C.

Das obige ist der detaillierte Inhalt vonWie kann man Duplikate in einem Array von Zahlen von 0 bis n-1 in O(n)-Zeit und O(1)-Raum finden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!