मान लीजिए हमारे पास शब्दों की एक गैर-खाली सूची है; हमें k सबसे अधिक बार आने वाले तत्व ढूंढने हैं। हमारा उत्तर उच्चतम से निम्नतम आवृत्ति के अनुसार क्रमबद्ध होना चाहिए। जब दो शब्दों की आवृत्ति समान होती है, तो कम वर्णमाला क्रम वाला शब्द पहले रखा जाएगा। इसलिए यदि सरणी ['the', 'sky', 'is', 'blue', 'the', 'weather', 'is', 'comfortable'] जैसी है, तो सबसे अधिक बार आने वाले शब्द ["is","the","blue"] हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- m नामक एक मैप परिभाषित करें
- v नामक एक प्राथमिकता कतार (priority queue) बनाएं
- i := 0 से n तक, जहां n शब्द सरणी का आकार है, फिर m[words[i]] को 1 से बढ़ाएं
- मैप में प्रत्येक तत्व e के लिए
- यदि v का आकार < k है, तो e को v में सम्मिलित करें
- अन्यथा यदि v.top का मान < e का मान है, तो v से शीर्ष तत्व हटाएं और e को v में सम्मिलित करें।
- अन्यथा यदि v.top का मान = e का मान है और v.top की कुंजी > e की कुंजी है, तो v से शीर्ष तत्व हटाएं, e को v में सम्मिलित करें
- res नामक एक सरणी परिभाषित करें
- जब तक v खाली नहीं है,
- temp := v का शीर्ष
- v से शीर्ष हटाएं
- temp की कुंजी को res सरणी में सम्मिलित करें
- 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"]
