C++ এ শীর্ষ K ঘন ঘন শব্দ

ধরুন আমাদের কাছে শব্দের একটি খালি তালিকা নেই; আমাদের k সবচেয়ে ঘন ঘন উপাদান খুঁজে বের করতে হবে। আমাদের উত্তর সর্বোচ্চ থেকে সর্বনিম্ন পর্যন্ত ফ্রিকোয়েন্সি অনুসারে সাজানো উচিত। যখন দুটি শব্দের একই ফ্রিকোয়েন্সি থাকে, তখন নিম্ন বর্ণানুক্রমিক শব্দটি প্রথমে বসানো হবে। সুতরাং যদি অ্যারেটি ['the', 'sky', 'is', 'blue', 'the', 'weather', 'is', 'comfortable'] এর মত হয়, তাহলে সবচেয়ে ঘন ঘন শব্দগুলি হল ["is", "the","blue"]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• m নামে একটি মানচিত্র সংজ্ঞায়িত করুন
• একটি অগ্রাধিকার সারি তৈরি করুন v
• এর জন্য i :=0 থেকে n, যেখানে n শব্দ অ্যারের আকার, তারপর m[words[i]] 1 দ্বারা বাড়ান
• মানচিত্রের প্রতিটি উপাদানের জন্য
  • যদি v
  • অন্যথায় যদি v.top-এর মান
  • অন্যথায় যদি v.top-এর মান =e-এর মান এবং v.top-এর কী হয়> e-এর কী, তাহলে v থেকে শীর্ষ উপাদান মুছে ফেলুন, v-তে e ঢোকান
• রেস নামে একটি অ্যারে সংজ্ঞায়িত করুন
• যখন v খালি নয়,
  • temp :=v এর শীর্ষ
  • v থেকে শীর্ষ মুছুন
  • Res অ্যারেতে temp-এর কী ঢোকান
• রেস অ্যারে বিপরীত করুন
• রিটার্ন রিটার্ন

উদাহরণ(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"]