এই সমস্যায় শব্দের একটি লিস্ট এবং একটি ইন্টিজার k দেওয়া থাকলে, সবচেয়ে বেশি ফ্রিকোয়েন্সি वाले kটি শব্দ বের করতে হবে। ফলাফল ফ্রিকোয়েন্সি অনুযায়ী ডিসেন্ডিং অর্ডারে সর্টেড থাকবে। ফ্রিকোয়েন্সি সমান হলে অ্যালফাবেটিক্যালি ছোট শব্দটি আগে থাকবে।
উদাহরণ: ["the","sky","is","blue","the","weather","is","comfortable"], k=3 -> আউটপুট ["is","the","blue"]।
সমাধানের পদ্ধতি (Heap + Map)
- ফ্রিকোয়েন্সি কাউন্ট করার জন্য
unordered_mapবাmapব্যবহার করুন। - কাস্টম কমপেরেটর সহ একটি মিন-হিপ (priority_queue) ব্যবহার করুন যাতে টপ
kটি বজায় থাকে।- কম্পেয়ার: ফ্রিকোয়েন্সি কম হলে ছোট, ফ্রিকোয়েন্সি সমান হলে লেক্সিকোগ্রাফিক্যালি বড়টি ছোট (তाकি সেটি পপ হয়ে যায়)।
- সব শব্দ প্রসেস করার পর হিপ থেকে পপ করে রিজাল্ট বানান এবং রিভার্স করুন।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(const pair<string, int>& a, const pair<string, int>& b) {
if (a.second != b.second) return a.second > b.second; // min-heap by freq
return a.first < b.first; // max-heap by lexicographical (larger string is "smaller" for min-heap)
}
};
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> freq;
for (auto& w : words) freq[w]++;
priority_queue<pair<string, int>, vector<pair<string, int>>, Comparator> pq;
for (auto& p : freq) {
pq.push(p);
if (pq.size() > k) pq.pop();
}
vector<string> res;
while (!pq.empty()) {
res.push_back(pq.top().first);
pq.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
void printVec(vector<string> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) cout << "\"" << v[i] << "\"" << (i+1==v.size()?"":", ");
cout << "]" << endl;
}
int main() {
Solution ob;
vector<string> v = {"the","sky","is","blue","the","weather","is","comfortable"};
printVec(ob.topKFrequent(v, 3));
return 0;
}
ইনপুট
["the","sky","is","blue","the","weather","is","comfortable"] 3
আউটপুট
["is", "the", "blue"]
