c++ - 首先按频率对字符串中的字符进行排序，然后按字母顺序对字符串中的字符进行排序

Question

给定一个字符串，我试图计算字符串中每个字母的出现次数，然后将它们出现的频率从高到低排序。然后，对于出现次数相似的字母，我必须按字母顺序对它们进行排序。

这是我到目前为止能够做的:

• 我创建了一个大小为 26 的 int 数组，对应于字母表中的 26 个字母，每个字母的值代表它在句子中出现的次数
• 我将这个数组的内容插入一个 vector 对 v，由 int 和 char (int 表示频率，char 表示实际字母)
• 我使用 std::sort(v.begin(), v.end());
对这个 vector 对进行了排序

在显示频率计数时，我只是用了一个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 = 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 . . .

如您所见，如果不是因为不正确的 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;
}

Answer 1

你可以分两步简化这个:

1. 先用一个map统计字符串中每个字符出现的次数:

   std::unordered_map<char, unsigned int> count;
   
   for( char character : string )
       count[character]++;
   

2. 使用该 map 的值作为比较标准:

   std::sort( std::begin( string ) , std::end( string ) , 
              [&]( char lhs , char rhs )
              {
                  return count[lhs] < count[rhs];
              }
            ); 
   

Here是在 ideone 上运行的工作示例。