Wie kann ich einen Algorithmus zum Sortieren von n Zeichenfolgen in O (dn) entwerfen, wobei d die Anzahl der Zeichen in einer längsten Zeichenfolge ist?Entwerfen eines Algorithmus zum Sortieren von n Zeichenfolgen in O (dn)
Sie können eine trie verwenden.
Erstellen Sie einen leeren Trie.
Schleife über alle Zeichenfolgen, und legen Sie sie darin.
Iterieren Sie alle Werte des Trie in der Reihenfolge und geben Sie sie aus (siehe Trie complexity and searching, wie unten von Jean-Baptiste Yunès vorgeschlagen).
Die Komplexität von 1 ist konstant. Die Komplexität von 2 und 3 ist O (dn).
3. Punkt ist nicht klar. Wie stellen Sie sicher, dass die Strings sortiert sind? –
@SauravSahu Es ist eine ziemlich einfache rekursive Funktion (siehe [hier] (http://stackoverflow.com/questions/13685687/how-to-print-all-words-in-a- trie) eine Implementierung). Beginnen Sie am Knoten, und besuchen Sie rekursiv alle untergeordneten Elemente, während Sie das aktuelle Präfix verfolgen. Wenn Sie ein Blatt treffen, geben Sie die gesamte Zeichenfolge entlang des Pfads aus. –
Ergänzung: http://stackoverflow.com/questions/13032116/trie-complexity-and-searching –