Le tri des caractères dans une chaîne, d'abord par la fréquence et par ordre alphabétique
Donné une chaîne, je suis en train de compter les occurrences de chaque lettre de la chaîne, puis le tri de leurs fréquences, de la plus haute à la plus basse. Ensuite, pour les lettres qui ont le même nombre d'occurrences, je dois les trier par ordre alphabétique.
Voici ce que j'ai pu faire jusqu'à présent:
- J'ai créé un
int
tableau de taille 26 correspondant aux 26 lettres de l'alphabet, avec des valeurs individuelles représentant le nombre de fois qu'il apparaît dans la phrase - J'ai poussé le contenu de ce tableau dans un vecteur de paires,
v
, deint
etchar
(int
pour la fréquence, etchar
pour la lettre) - J'ai trié ce vecteur de paires à l'aide de
std::sort(v.begin(), v.end());
Dans l'affichage de la fréquence de comptage, j'ai simplement utilisé une boucle for en commençant par la dernière index pour afficher le résultat de la plus haute à la plus basse. Je vais avoir des problèmes, cependant, en ce qui concerne ces lettres ayant des fréquences similaires, parce que j'ai besoin de les afficher dans l'ordre alphabétique. J'ai essayé en utilisant une étude de boucle à l'intérieur de la boucle de départ avec l'indice le plus bas et à l'aide d'une instruction conditionnelle afin de vérifier si sa fréquence est la même que la boucle externe. Cela semblait fonctionner, mais mon problème est que je n'arrive pas à comprendre comment contrôler ces boucles de sorte que les sorties redondantes seront évités. Pour comprendre ce que je dis, veuillez voir cet exemple de sortie:
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 . . .
Comme vous pouvez le voir, il aurait été bien si ce n'était pas pour les sorties redondantes provoquée par le mauvais pour les boucles.
Si vous pouvez suggérer des plus efficaces ou mieux implémentations quant à mon problème, alors je serais très apprécier aussi longtemps qu'ils ne sont pas trop compliquées ou trop avancé comme je suis juste un C++ débutant.
Si vous avez besoin de voir mon code, le voici: c'est
#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;
}
Vous pouvez également utiliser un
map<char, int>
L., mais même si j'ai utilisé une carte, je ne serait pas encore en mesure de trier ses valeurs directement, ai-je le droit? Merci!
OriginalL'auteur makki | 2013-12-22
Vous devez vous connecter pour publier un commentaire.
Si vous voulez plus haute fréquence, puis plus bas de la lettre, un moyen facile pour stocker des valeurs négatives pour la fréquence, puis le nier après tri. Un moyen plus efficace serait de modifier la fonction utilisée pour le tri, mais c'est un peu plus compliqué:
OriginalL'auteur Yakk - Adam Nevraumont
Vous pouvez simplifier beaucoup, en deux étapes:
De la première utilisation d'une carte de compter le nombre d'occurrences de chaque caractère dans la chaîne:
Utiliser les valeurs de cette carte comme critères de comparaison:
Ici est un exemple de travail de course à ideone.
Ce code a un bug, je ne sais pas où exactement le genre échoue, mais essayez cette chaîne "AZBIPTOFTJCJJIK" La sortie est JJJITTIAZBPOFCK Voir le "je" personnage étant inséré dans les deux non-consécutives places!
OriginalL'auteur Manu343726
(Publié sur le nom de l'OP.)
Merci pour les réponses des gens formidables ici à Débordement de Pile, j'ai enfin réussi à régler mon problème. Voici mon code final au cas où quelqu'un est intéressé ou pour de futures références de personnes qui pourraient être coincés dans le même bateau:
Exemple de sortie:
En gros, j'ai juste suivi les conseils de @OliCharlesworth et mis en œuvre un custom comparateur grâce à l'aide de ce guide: Un Pointeur de Fonction comme Fonction de Comparaison.
Bien que je suis assez sûr que mon code peut être rendue plus efficace, je suis toujours très heureux avec les résultats.
OriginalL'auteur
À l'aide d'un
unordered_map
pour le comptage des caractères, tel que suggéré par @Manu343726 est une bonne idée. Toutefois, afin de produire votre triés en sortie, une autre étape est nécessaire.Ma solution est aussi dans C++11 et utilise un expression lambda. De cette façon, vous n'avez ni besoin de définir une coutume struct ni une fonction de comparaison. Le code est presque terminée, j'ai juste sauté à la lecture de l'entrée:
De sortie:
Note 1: au Lieu d'insérer chaque élément de la
unordered_map
dans leset
, il peut être plus efficace d'utiliser la fonctionstd::transform
oustd:copie
, mais mon code est au moins à court.Note 2: la Place de l'aide personnalisée triés
set
qui maintient l'ordre que vous souhaitez, il peut être plus efficace d'utiliser un vecteur de paires et de régler une fois à la fin, mais votre solution est déjà semblable à cela.Code sur Ideone
OriginalL'auteur honk