Eine Reihe von Zeichen sortieren

Question

Hier ist eine Interviewfrage, die ich hatte.

Eingabe: Eine Zeichenkette (ASCII), könnte ein Satz sein. Da kann man düsen. Ausgabe: Sortierte in der Reihenfolge der ASCII-Wert

Erwartete Komplexität: Lineare Zeit und konstanter zusätzlicher Raum

Mein Gedanke eine Art Eimer zu tun, war eine Art, wo Sie eine Größe 256 Array und dann verwenden, aber wenn Du hast dann Duplikate, wie würde das gehandhabt? Würde dies als konstanter Raum betrachtet werden? Ich denke, es wäre, weil Sie nur ein Array mit 256 Größen verwenden würden, und dass es nicht mit der Größe der Eingabe wachsen würde.

Ich möchte nicht den spezifischen Code, wie ich das gerne selbst tun würde, aber alle Hinweise wären hilfreich!

Answer 1

Die Lösung für dieses Problem ist counting sort.

Sie hätten ein Array der Größe 128 und alle Werte werden auf 0 initialisiert. Verwenden Sie den Ascii-Wert eines Zeichens, um in das Array zu indizieren, und inkrementieren Sie den Array-Wert.

Die sortierte Sequenz würde nur erzeugt, indem man das Array der Größe 128 durchquert, wo man nur das Zeichen des ASCII-Wertes i ausgibt, wenn Array [i] ungleich Null ist und der Wert die Häufigkeit des zu druckenden Zeichens angibt .

Sie haben Recht, das ist eine konstante Größe O (1) und lineare Zeit O (N) -Algorithmus.