在 C++ 中按频率对字符排序

假设我们有一个字符串，我们需要根据频率对字符进行排序。因此，如果字符串类似于“abbbacbcc”，则输出将为“bbbbcccaa”

为了解决此问题，我们将遵循以下步骤 -

  • 创建一个名为 v 的对数组，创建一个地图 m
  • 对于字符串中的所有字符，
    • 将 m[character] 的值增加 1
  • i := 地图的第一个元素
  • while 地图有元素
    • 将 (i.second, i.first) 插入到 v 中
    • 并将 i 增加以指向下一个元素
  • 对向量 v 进行排序
  • ans := 一个空字符串
  • 对于 i := 0 到 v 的大小
    • t := v[i] 的第一个元素
    • while t 不为 0
      • ans := ans + v[i] 的第二部分
      • 将 t 减小 1
  • 返回 ans

示例

让我们看下面的实现来获得更好的理解 -

 在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   static bool cmp(pair <int, char> a, pair <int, char> b){
      return a.first < b.first;
   }
   string frequencySort(string s) {
      vector < pair <int, char> > v;
      map <char, int> m;
      for(int i = 0; i < s.size(); i++){
         m[s[i]]++;
      }
      map <char, int> :: iterator i = m.begin();
      while(i != m.end()){
         v.push_back({i->second, i->first});
         i++;
      }
      sort(v.rbegin(), v.rend(), cmp);
      string ans = "";
      for(int i = 0; i < v.size(); i++){
         int t = v[i].first;
         while(t--)ans += v[i].second;
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << ob.frequencySort("abbbacbcc");
}

输入

"abbbacbcc"

输出

bbbbcccaa

更新于：28-Apr-2020

2K+ 浏览量

开启您的 职业生涯

完成课程后获得认证

开始使用
广告