Cyclic Sort
Gegeben eine Liste mit n Objekten. Jedem Objekt wurde beim Erstellen eine eindeutige Nummer von 1 bis n zugewiesen, basierend auf der Reihenfolge, in der es erstellt wurde.
Erstellen Sie eine Funktion, die Objekte anhand der fortlaufenden Anzahl von O (n) an Ort und Stelle sortiert. Es ist keine zusätzliche Datenstruktur erforderlich. Nehmen wir der Einfachheit halber an, Sie erhalten eine Liste von Ganzzahlen, die nur fortlaufende Zahlen enthalten. Jede Zahl ist jedoch tatsächlich ein Objekt.
Input: [3, 1, 5, 4, 2] Output: [1, 2, 3, 4, 5]
Input: [2, 6, 4, 3, 1, 5] Output: [1, 2, 3, 4, 5, 6]
Input: [1, 5, 6, 4, 3, 2] Output: [1, 2, 3, 4, 5, 6]
Solution Wie Sie wissen, enthält die Liste Zahlen im Bereich 1-n. Nutzen Sie diese Tatsache, um eine effiziente Methode zum Sortieren von Zahlen zu finden. Alle Zahlen sind eindeutig, sodass Sie jede Zahl an der richtigen Position platzieren können. Das heißt, 1 wird am Index 0 platziert, 2 wird am Index 1 platziert und so weiter.
Um eine Zahl (oder ein Objekt im Allgemeinen) im richtigen Index zu platzieren, müssen Sie sie zuerst finden. Wenn Sie zuerst die Nummer finden und an der richtigen Stelle platzieren, O (N ^ 2), ist dies nicht akzeptabel.
Wiederholen Sie stattdessen die Liste mit jeweils einer Nummer. Wenn sich die aktuelle Nummer nicht im richtigen Index befindet, ersetzen Sie sie durch die Nummer im richtigen Index. Auf diese Weise werden alle Zahlen nachgeschlagen, in den richtigen Index eingefügt und die gesamte Liste sortiert.
def cyclic_sort(nums):
i = 0
while i < len(nums):
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i] # swap
else:
i += 1
return nums
def main():
print(cyclic_sort([3, 1, 5, 4, 2]))
print(cyclic_sort([2, 6, 4, 3, 1, 5]))
print(cyclic_sort([1, 5, 6, 4, 3, 2]))
main()
Recommended Posts