Ich versuche eine Zeichenkette nach der Anzahl der Vorkommen jedes Zeichens zu sortieren, am häufigsten am Anfang und am seltensten am Ende. Nach dem Sortieren müsste ich alle Zeichenwiederholungen entfernen. Da Beispiele immer klarer sind, sollte das Programm Folgendes tun:
%Vor%In diesem Fall sollte die Methode 'sortByCharacterOccurrencesAndTrim' zurückgeben:
%Vor%Wenn 2 Zeichen das gleiche Vorkommen haben, spielt ihre Reihenfolge in der zurückgegebenen Zeichenfolge keine Rolle. So kann "habefcdg" auch gleich "habfecgd" sein, weil sowohl "f" als auch "e" dreimal vorkommen und sowohl "d" als auch "g" einmal vorkommen.
%Vor%Hinweis: Ich möchte in diesem Fall darauf hinweisen, dass Leistung wichtig ist . Daher würde ich die effizienteste Methode bevorzugen. Ich sage das, weil die String-Länge von 1 bis zur maximalen Länge reichen kann (was ich denke, ist gleich wie Integer.MAX_VALUE, aber nicht sicher), also möchte ich mögliche Engpässe minimieren.
"Eine Karte und mehrere While-Loops" ist sicherlich der einfachste Weg und wahrscheinlich sehr schnell. Die Idee ist:
%Vor%Aber 100.000.000 Kartensuchen könnten ziemlich teuer werden. Sie könnten es möglicherweise beschleunigen, indem Sie ein Array von 65.536 Ganzzahlen (oder 128 Zeichen, wenn es sich um ASCII handelt) erstellen. Dann:
%Vor%Dann gehen Sie durch dieses Array und erstellen eine Karte der Zeichen mit Nicht-Null-Zählungen:
%Vor%Sortieren Sie dann die Karte in absteigender Reihenfolge und geben Sie die Zeichen in dieser Reihenfolge aus.
Das könnte eine ganze Weile schneller sein, weil die Indexierung in ein Array 100.000.000 mal viel schneller ist als 100.000.000 Kartensuchen.
Hinweis: Dies ist keine Antwort, sondern zeigt einfach den Leistungstest-Antwortcode von Jim Mischel und Óscar López (mit parallelen Streams als Antwort auf Kommentar von OP ).
%Vor%Beispielausgabe
%Vor%Nur zum Spaß (und ich behaupte nicht, dass dies die effizienteste Lösung ist): Wie wäre es mit einigen Java 8 lambdas + parallelen Streams?
%Vor%Wenn Sie eine super-effiziente Lösung wollen, können Sie den obigen Algorithmus mit expliziten Loops neu schreiben, aber das ist eine Menge Code und es ist spät für mich :). Die Idee wird jedoch die gleiche sein: Erstellen Sie eine char Frequenzkarte, sortieren Sie nach Häufigkeit in absteigender Reihenfolge und bauen Sie eine Zeichenfolge mit den Zeichen.
Tags und Links string java performance sorting