Сортировка символов в строке сначала по частоте, а затем по алфавиту
Учитывая строку, я пытаюсь подсчитать вхождение каждой буквы в строке, а затем отсортировать их частоту от самой высокой до самой низкой. Затем для писем с одинаковым количеством вхождений я должен отсортировать их по алфавиту.
Вот что я смог сделать до сих пор:
- Я создал
intмассив размером 26, соответствующий 26 буквам алфавита с отдельными значениями, представляющими количество раз, которое он появился в предложении - Я поместил содержимое этого массива в вектор пар,
vизintа такжеchar(intдля частоты, иcharдля самого письма) - Я отсортировал этот вектор пар, используя
std::sort(v.begin(), v.end());
При отображении счетчика частоты я просто использовал цикл for, начиная с последнего индекса, чтобы отобразить результат от наивысшего к низшему. У меня, однако, возникают проблемы с тем, что буквы имеют одинаковую частоту, потому что они нужны в алфавитном порядке. Я попытался использовать вложенный цикл for с внутренним циклом, начиная с самого низкого индекса, и использовать условный оператор, чтобы проверить, совпадает ли его частота с внешним циклом. Казалось, это работает, но моя проблема в том, что я не могу понять, как управлять этими циклами, чтобы избежать лишних выходов. Чтобы понять, что я говорю, посмотрите этот пример вывода:
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 = 1Sorted 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 . . .
Как видите, было бы хорошо, если бы не было избыточных выходов, вызванных неправильными циклами for.
Если вы можете предложить более эффективные или лучшие реализации в отношении моей заботы, я был бы очень признателен, если бы они не были слишком сложными или слишком продвинутыми, поскольку я всего лишь новичок в C ++.
Если вам нужно увидеть мой код, вот он:
#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;
}
Решение
Если вам нужна самая высокая частота, а затем самая низкая буква, проще всего было бы сохранить отрицательные значения частоты, а затем отменить ее после сортировки. Более эффективным способом было бы изменить функцию, используемую для сортировки, но это немного сложнее:
struct sort_helper {
bool operator()(std::pair<int,char> lhs, std::pair<int,char> rhs) const{
return std::make_pair(-lhs.first,lhs.second)<std::make_pair(-rhs.first,rhs.second);
}
};
std::sort(vec.begin(),vec.end(),sort_helper());
Другие решения
Вы можете упростить это за два шага:
-
Сначала используйте карту для подсчета количества вхождений каждого символа в строке:
std::unordered_map<char, unsigned int> count; for( char character : string ) count[character]++; -
Используйте значения этой карты в качестве критериев сравнения:
std::sort( std::begin( string ) , std::end( string ) , [&]( char lhs , char rhs ) { return count[lhs] < count[rhs]; } );
Вот это рабочий пример работает на ideone.
(Опубликовано от имени ОП.)
Благодаря откликам удивительных людей здесь, в Stack Overflow, я наконец-то смог решить мою проблему. Вот мой окончательный код на случай, если кому-то будет интересно, или для будущих ссылок людей, которые могут застрять в одной лодке:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Letters
{
Letters() : freq(0){}
Letters(char letter,int freq) {
this->freq = freq;
this->letter = letter;
}
char letter;
int freq;
};
bool Greater(const Letters& a, const Letters& b)
{
if(a.freq == b.freq)
return a.letter < b.letter;
return a.freq > b.freq;
}
int main () {
cout<<"Enter a string: ";
string input;
getline(cin, input);
vector<Letters> count;
int letters[26]= {0};
for (int x = 0; x < input.length(); x++) {
if (isalpha(input[x])) {
int c = tolower(input[x] - 'a');
letters[c]++;
}
}
for (int x = 0; x < 26; x++) {
if (letters[x] > 0) {
char c = x + 'a';
count.push_back(Letters(c, letters[x]));
}
}
cout<<"\nUnsorted list..\n";
for (int x = 0 ; x < count.size(); x++) {
cout<<count[x].letter<< " = "<< count[x].freq<<"\n";
}
std::sort(count.begin(),count.end(),Greater);
cout<<"\nSorted list according to frequency then alphabetically..\n";
for (int x = 0 ; x < count.size(); x++) {
cout<<count[x].letter<< " = "<< count[x].freq<<"\n";
}
system("pause");
return 0;
}
Пример вывода:
Enter a string: hello world
Unsorted list..
d = 1
e = 1
h = 1
l = 3
o = 2
r = 1
w = 1
Sorted list according to frequency then alphabetically..
l = 3
o = 2
d = 1
e = 1
h = 1
r = 1
w = 1
Press any key to continue . . .
Я просто следовал совету @OliCharlesworth и реализовал собственный компаратор с помощью этого руководства: Указатель на функцию как функция сравнения.
Хотя я уверен, что мой код все еще можно сделать более эффективным, я по-прежнему доволен результатами.
Используя unordered_map для подсчета символов, как предложено @ Manu343726, это хорошая идея. Однако для получения отсортированного вывода требуется еще один шаг.
Мое решение также в C ++ 11 и использует лямбда-выражение. Таким образом, вам не нужно ни определять пользовательскую структуру, ни функцию сравнения. Код почти завершен, я просто пропустил чтение ввода:
#include <unordered_map>
#include <iostream>
#include <set>
int main() {
string input = "hello world";
unordered_map<char, unsigned int> count;
for (char character : input)
if (character >= 'a' && character <= 'z')
count[character]++;
cout << "Unsorted list:" << endl;
for (auto const &kv : count)
cout << kv.first << " = " << kv.second << endl;
using myPair = pair<char, unsigned int>;
auto comp = [](const myPair& a, const myPair& b) {
return (a.second > b.second || a.second == b.second && a.first < b.first);
};
set<myPair, decltype(comp)> sorted(comp);
for(auto const &kv : count)
sorted.insert(kv);
cout << "Sorted list according to frequency then alphabetically:" << endl;
for (auto const &kv : sorted)
cout << kv.first << " = " << kv.second << endl;
return 0;
}
Выход:
Несортированный список:
г = 1
ч = 1
е = 1
д = 1
o = 2
ш = 1
l = 3
Список отсортирован по частоте, затем по алфавиту:
l = 3
o = 2
д = 1
е = 1
ч = 1
г = 1
ш = 1
Примечание 1: вместо вставки каждого элемента из unordered_map в set, было бы более эффективно использовать функцию std::transform или же std:copy, но мой код по крайней мере короткий.
Примечание 2: вместо использования отсортированного set который поддерживает требуемый порядок, может быть более эффективно использовать вектор пар и сортировать его один раз в конце, но ваше решение уже похоже на это.