Sortieren von Zeichen in einer Zeichenfolge zunächst nach Häufigkeit und dann alphabetisch
Gegeben ein string, ich versuche, die Anzahl des Vorkommens der einzelnen Buchstaben in der Zeichenfolge, und Sortieren Sie anschließend Ihre Frequenz von der höchsten bis zur niedrigsten. Dann, für die Buchstaben, die ähnliche Anzahl der vorkommen, ich habe Sie alphabetisch zu ordnen.
Hier ist, was ich in der Lage gewesen zu tun, so weit:
- Erstellte ich eine
int
array der Größe 26, entsprechend den 26 Buchstaben des Alphabets mit den einzelnen Werten für die Anzahl der Male erschien es im Satz - Schob ich den Inhalt dieses Arrays in einen Vektor von Paaren
v
, derint
undchar
(int
für die Frequenz, und diechar
für den eigentlichen Brief) - Sortierte ich diese Vektor von Paaren mit
std::sort(v.begin(), v.end());
In der Anzeige die Frequenz zählen, ich habe gerade verwendet eine for-Schleife, beginnend mit dem letzten index zeigt ein Ergebnis von der höchsten bis zur niedrigsten. Ich habe Probleme, allerdings mit Bezug auf jene Buchstaben, die ähnliche Frequenzen, da muss ich Ihnen in alphabetischer Reihenfolge angezeigt. Ich habe versucht, mit Hilfe einer geschachtelten for-Schleife die innere Schleife beginnend mit dem niedrigsten index und das verwenden eine bedingte Anweisung, um zu überprüfen, ob seine Frequenz ist die gleiche wie die äußere Schleife. Dies schien zu funktionieren, aber mein problem ist, dass ich kann nicht scheinen, um herauszufinden, wie man diese Schleifen, so dass redundante Ergebnisse vermieden werden. Um zu verstehen, was ich sage, sehen Sie sich bitte die Beispiel-Ausgabe:
Enter a string: hello world
Pushing the array into a vector pair v:
d = 1
e = 1
h = 1
l = 3
o = 2
r = 1
w = 1
Sorted first according to frequency then alphabetically:
l = 3
o = 2
d = 1
e = 1
h = 1
r = 1
w = 1
d = 1
e = 1
h = 1
r = 1
d = 1
e = 1
h = 1
d = 1
e = 1
d = 1
Press any key to continue . . .
Wie Sie sehen können, es wäre gut, wenn es nicht für die redundante Ausgänge, hervorgerufen durch die fehlerhafte for-Schleifen.
Wenn Sie vorschlagen können, effizienter oder besser-Implementierungen mit Bezug auf mein Anliegen, dann würde ich es zu schätzen wissen, solange Sie nicht zu kompliziert oder zu Fortgeschritten, als ich gerade einen C++ - Anfänger.
Wenn Sie brauchen, um zu sehen, mein code hier ist:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cout<<"Enter a string: ";
string input;
getline(cin, input);
int letters[26]= {0};
for (int x = 0; x < input.length(); x++) {
if (isalpha(input[x])) {
int c = tolower(input[x] - 'a');
letters[c]++;
}
}
cout<<"\nPushing the array into a vector pair v: \n";
vector<pair<int, char> > v;
for (int x = 0; x < 26; x++) {
if (letters[x] > 0) {
char c = x + 'a';
cout << c << " = " << letters[x] << "\n";
v.push_back(std::make_pair(letters[x], c));
}
}
//Sort the vector of pairs.
std::sort(v.begin(), v.end());
//I need help here!
cout<<"\n\nSorted first according to frequency then alphabetically: \n";
for (int x = v.size() - 1 ; x >= 0; x--) {
for (int y = 0; y < x; y++) {
if (v[x].first == v[y].first) {
cout << v[y].second<< " = " << v[y].first<<endl;
}
}
cout << v[x].second<< " = " << v[x].first<<endl;
}
system("pause");
return 0;
}
- Sie können dies lösen, in einem einzigen Schritt, indem Sie Ihre Art mit einem benutzerdefinierten Komparator (siehe en.cppreference.com/w/cpp/algorithm/sort für ein Beispiel).
- Sie können auch ein
map<char, int>
- L., aber selbst wenn ich eine Karte, die ich noch nicht in der Lage zu Sortieren Sie Ihre Werte direkt, hab ich Recht? Danke!
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wenn Sie wollen höchste Frequenz, die dann niedrigste Brief, eine einfache Möglichkeit wäre zum speichern von negativen Werten für Frequenz, dann negieren Sie, nachdem Sie Art. Ein effizienter Weg wäre, ändern der Funktion für die Sortierung verwendet, aber das ist einen Hauch schwieriger:
Könnte man vereinfachen, eine Menge, die in zwei Schritten:
Verwenden Sie zunächst eine Karte, um die Anzahl der vorkommen der einzelnen Zeichen in der Zeichenfolge:
Verwenden Sie die Werte für diese Karte als Vergleich Kriterien:
Hier ist ein funktionierendes Beispiel läuft bei ideone.
(Veröffentlicht im Namen des OP.)
Danke für die Antworten von den tollen Menschen hier bei Stack Overflow, ich war schließlich in der Lage, zu beheben mein problem. Hier ist meine Letzte code falls es jemanden interessiert oder für zukünftige Referenzen von Menschen, die möglicherweise stecken im selben Boot:
Beispiel-Ausgabe:
Ich grundsätzlich nur folgte dem Rat von @OliCharlesworth und implementiert eine benutzerdefinierte Komparator-durch die Hilfe von dieser Anleitung: Einen Funktionszeiger als Vergleich-Funktion.
Obwohl ich mir ziemlich sicher bin, dass mein code noch effizienter gemacht werden, ich bin immer noch ziemlich glücklich mit den Ergebnissen.
Mit einem
unordered_map
zum zählen von Zeichen wie vorgeschlagen von @Manu343726 ist eine gute Idee. Jedoch, um zu produzieren Ihr sortiert die Ausgabe, ist ein weiterer Schritt erforderlich ist.Meine Lösung ist auch in C++11 und verwendet eine lambda-Ausdruck. Auf diese Weise, die Sie weder brauchen, um eine benutzerdefinierte Struktur, die noch eine Vergleich-Funktion. Der code ist fast abgeschlossen, die ich einfach übersprungen-Lesen der Eingabe:
Ausgabe:
Hinweis 1: Anstelle von einfügen jedes element aus der
unordered_map
in dieset
, könnte es effizienter sein, um die Funktion zu verwendenstd::transform
oderstd:copy
, aber mein code ist zumindest kurz.Hinweis 2: Anstatt eine benutzerdefinierte sortiert
set
, die behauptet, die Reihenfolge, die Sie wollen, könnte es effizienter sein, zu verwenden einen Vektor von Paaren und Sortieren Sie einmal am Ende, aber deine Lösung ist schon sehr ähnlich zu diesem.Code auf Ideone