K từ thường dùng hàng đầu trong C ++

Giả sử chúng ta có một danh sách các từ không rỗng; chúng ta phải tìm k phần tử thường xuyên nhất. câu trả lời của chúng tôi nên được sắp xếp theo tần suất từ ​​cao nhất đến thấp nhất. Khi hai từ có cùng tần số, thì từ có thứ tự bảng chữ cái thấp hơn sẽ được đặt ở đầu tiên. Vì vậy, nếu mảng giống như ['the', 'sky', 'is', 'blue', 'the', 'weather', 'is', 'thoải mái'], vì vậy các từ phổ biến nhất là ["is", "the", "blue"]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ được gọi là m
• tạo một hàng đợi ưu tiên v
• for i:=0 to n, trong đó n là kích thước của mảng từ, sau đó tăng m [words [i]] lên 1
• cho mỗi phần tử e trong bản đồ
  • nếu kích thước của v
  • ngược lại, nếu giá trị của v.top
  • ngược lại nếu giá trị của v.top là =giá trị của e và khóa của v.top là> khóa của e, thì xóa phần tử trên cùng khỏi v, chèn e vào v
• xác định một mảng được gọi là res
• while v không trống,
  • temp:=top of v
  • xóa hàng đầu khỏi v
  • chèn khóa tạm thời vào mảng res
• đảo ngược mảng res
• trả lại res

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

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