Sortiere eine Reihe von n Zahlen zwischen [0,2k], wobei zwischen jedem Paar existiert: | Ai-Aj |> = k/n

Question

Sei A1,A2,...,An reelle Zahlen zwischen [0,2k] (k ist konstant). Es ist bekannt, dass für jedes Paar Ai,AJ dann |Ai-Aj|>=k/n,

Beschreiben Sie einen Algorithmus sortiert die Zahlen in O(n) Laufzeit Worst-Case.

Ich weiß, dass die Antwort Eimer-sort sein sollte. Kann nicht verstehen, warum, Und wenn ja, wie wähle ich die richtige Menge an Eimern? Wie hilft die |Ai-Aj|>=k/n eigentlich?

Answer 1

Die Bedingung | A _i - A _j | ≥ k/n bedeutet, dass, wenn Sie den Bereich [0, 2k] in 2n verschiedene Buckets aufteilen (von denen jeder die Größe 2k/2n = k/n hat), 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 von weniger als k/n und kann daher höchstens eine Zahl enthalten.

Sie dann die Nummern durch Verwendung einer Bucketsort Algorithmus sortiert werden kann:

• Eine Anordnung von 3N Schaufeln, die jeweils den Bereich [(2k/3N) i, (2k/3N) (i + 1))
• Für jede Nummer:
  • Teilen Sie diese Zahl mit (2k/3n), um zu bestimmen, in welchen Bucket sie platziert werden soll.
  • Platzieren Sie die Nummer in diesem Bereich.
• Für jede Schaufel:
  • Wenn dieser nicht leer ist bucket, schreiben die Zahl in dem Eimer in den Ergebnis-Array.

Der erste Schritt dauert O (n) Zeit, da man ein Array der Größe 3N ist zu schaffen. 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 Buckets besuchen.

Hoffe, das hilft!