C++ में शीर्ष K फ़्रीक्वेंट वर्ड्स

मान लीजिए कि हमारे पास शब्दों की एक गैर-रिक्त सूची है; हमें k सबसे अधिक बार आने वाले तत्वों को खोजना होगा। हमारे उत्तर को आवृत्ति के अनुसार उच्चतम से निम्नतम तक क्रमबद्ध किया जाना चाहिए। जब दो शब्दों की बारंबारता समान हो तो निम्न वर्णक्रम वाले शब्द को पहले रखा जाएगा। तो यदि सरणी ['द', 'आकाश', 'है', 'नीला', 'द', 'मौसम', 'है', 'आरामदायक'] की तरह है, तो सबसे अधिक बार आने वाले शब्द हैं ["is", "द", "ब्लू"]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• m नामक एक मानचित्र को परिभाषित करें
• एक प्राथमिकता कतार बनाएं v
• i :=0 से n के लिए, जहां n शब्द सरणी का आकार है, फिर m[words[i]] को 1 से बढ़ाएं
• नक्शे में प्रत्येक तत्व ई के लिए
  • यदि v
  • अन्यथा यदि v.top का मान
  • अन्यथा यदि v.top का मान =e का मान और v.top की कुंजी> e की कुंजी है, तो v से शीर्ष तत्व को हटा दें, e को v में डालें
• रेस नामक एक सरणी को परिभाषित करें
• जबकि v खाली नहीं है,
  • अस्थायी:=वी के शीर्ष
  • v से शीर्ष हटाएं
  • 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"]