Sei A1,A2,...,An reelle Zahlen zwischen [0,2k] (k ist konstant). Es ist bekannt, dass für jedes Paar von Ai,AJ dann |Ai-Aj|>=k/n ,
Beschreiben Sie einen Algorithmus, der die Zahlen in O(n) runtime worst-case sortiert.
Ich weiß, dass die Antwort Eimer-Art sein sollte. Kann nicht verstehen, warum, Und wenn ja, wie wähle ich die richtige Menge an Eimern? Wie hilft das |Ai-Aj|>=k/n tatsächlich?
Die Bedingung | A i - A j | ≥ k / n bedeutet, dass, wenn Sie den Bereich [0, 2k] in 2n verschiedene Buckets aufteilen (jeder hat die Größe 2k / 2n = k / n), dann kann es höchstens eine Zahl in jedem Bereich geben (außer möglicherweise if) die Zahlen befinden sich an den Endpunkten der Buckets.) Wenn Sie die Buckets enger erstellen (z. B. durch Erstellen von 3n Buckets), hat jeder Bucket eine Größe kleiner als k / n und kann daher höchstens eine Zahl enthalten.
Sie können die Zahlen dann mithilfe eines Bucket-Sortieralgorithmus sortieren:
Der erste Schritt dauert O (n) Zeit, da Sie ein Array der Größe 3n erstellen. Der nächste Schritt benötigt Zeit O (n), da Sie jede der O (n) -Zahlen einmal besuchen und O (1) bei jedem Schritt arbeiten. Der letzte Schritt dauert auch O (n) Zeit, da Sie insgesamt 3n Eimer besuchen.
Hoffe, das hilft!
Tags und Links algorithm sorting big-o bucket-sort