C ++中排名前K的常用词

假设我们有一个非空的单词列表；我们必须找到k个最频繁的元素。我们的答案应该按照频率从高到低的顺序排序。当两个单词具有相同的频率时，则将首先按字母顺序排列较低的单词。因此，如果数组像['the'，'sky'，'is'，'blue'，'the'，'weather'，'is'，'comfortable']一样，则最常用的单词是[“ is”， “ the”，“ blue”]

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

• 定义一张称为m的映射

• 创建一个优先级队列v

• 对于i：= 0到n，其中n是单词数组的大小，然后将m [words [i]]加1

• 对于映射中的每个元素e

• 如果v <k的大小，则将e插入v

• 否则，如果v.top的值<e的值，则从v中删除top元素并将e插入v。

• 否则，如果v.top的值为= e的值并且v.top的键为> e的键，则从v中删除top元素，将e插入v

• 定义一个称为res的数组

• 当v不为空时，

• temp：= v的顶部

• 从v删除top

• 将临时键插入res数组

• 反转res数组

• 返回资源

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
struct Comparator{
   bool operator()(pair <string ,int> a, pair <string, int> b){
      if(a.second != b.second) return !(a.second < b.second);
         return !(a.first > b.first);
   }
};
class Solution {
public:
   static bool cmp(pair <string, int> a, pair <string, int> b){
      if(a.second != b.second) return a.second > b.second;;
         return a.first < b.first;
   }
   vector<string> topKFrequent(vector<string>& words, int k) {
      map<string, int> m;
      priority_queue < pair <string, int>, vector < pair <string, int> >, Comparator > v;
      for(int i = 0; i < words.size(); i++){
         m[words[i]]++;
      }
      map<string, int> :: iterator i = m.begin();
      while(i != m.end()){
         if(v.size() < k){
            v.push(*i);
         }
         else if(v.top().second < i->second){
            v.pop();
            v.push(*i);
         }
         else if(v.top().second == i->second && v.top().first > i->first){
            v.pop();
            v.push(*i);
         }
         i++;
      }
      vector <string> res;
      while(!v.empty()){
         pair <string, int> temp = v.top();
         v.pop();
         res.push_back(temp.first);
      }
      reverse(res.begin(), res.end());
      return res;
   }
};
main(){
   Solution ob;
   vector<string> v = {"the", "sky", "is", "blue", "the", "weather", "is", "comfortable"};
   print_vector(ob.topKFrequent(v, 3));
}

输入项

["the", "sky", "is", "blue", "the", "weather", "is", "comfortable"]
3

输出结果

["is","the","blue"]