ধরুন আমাদের কাছে N আকারের পূর্ণসংখ্যার একটি অ্যারে এবং একটি কী K রয়েছে। আমাদের কাজ হল অ্যারের উপরের K সবচেয়ে ঘন ঘন উপাদানটি প্রিন্ট করা। উদাহরণস্বরূপ,
ইনপুট-1 −
N = 6
K = 2
arr[ ] = {1 ,1, 1, 2, 2, 3} আউটপুট −
1 2
ব্যাখ্যা − প্রদত্ত পূর্ণসংখ্যার বিন্যাসে, শীর্ষ K=2 উপাদান যার কম্পাঙ্ক অ্যারেতে সবচেয়ে বেশি তা হল {1,2}৷
ইনপুট-2 −
N = 2
K = 1
arr[ ] = {1, 2} আউটপুট −
1
ব্যাখ্যা − প্রদত্ত পূর্ণসংখ্যার অ্যারেতে, উপরের K=1 উপাদানগুলির কম্পাঙ্ক অ্যারেতে সবচেয়ে বেশি হয় {1}৷
এই সমস্যা সমাধানের পদ্ধতি
প্রদত্ত পূর্ণসংখ্যার অ্যারেতে, আমাদের সেই সংখ্যাগুলি খুঁজে বের করতে হবে এবং ফেরত দিতে হবে যেগুলি প্রদত্ত অ্যারেতে বেশিরভাগ সময় পুনরাবৃত্তি হয়। কী K অ্যারের উপরের K উপাদানটি দেখায় যা আমাদের অ্যারে অতিক্রম করার সময় ফিরে আসতে হবে।
পদ্ধতি খুব সহজ. আমরা বর্তমান উপাদান হিসাবে একটি কী এবং সেই নির্দিষ্ট সংখ্যার উপস্থিতি হিসাবে একটি মান সহ একটি হ্যাশ টেবিল তৈরি করব। পুরো মানচিত্রটি সাজানোর পরে এবং প্রতিটি উপাদানের উপস্থিতি খুঁজে বের করার পরে, প্রথম K সর্বাধিক ঘন ঘন উপাদানগুলির আউটপুট ফলাফল ফেরত দিন৷
-
N কে ইনপুট এবং N উপাদানের অ্যারে হিসাবে নিন।
-
একটি ফাংশন topKfrequent(int *arr, int k) যা একটি arr[ ] এবং K কে ইনপুট হিসাবে নেয় এবং উপরের K ঘন ঘন উপাদানগুলি প্রদান করে।
-
একটি কী এবং জোড়া হিসাবে সমস্ত উপাদান এবং তাদের সংঘটনের একটি হ্যাশম্যাপ তৈরি করুন৷
৷ -
হ্যাশম্যাপে সমস্ত মান সাজান।
-
একটি বুল হেল্পার ফাংশন মান অনুসারে মানচিত্রকে সাজাতে সাহায্য করে এবং নিম্নোক্ত ক্রমে মান প্রদান করে।
-
হ্যাশম্যাপের সমস্ত মানের উপর পুনরাবৃত্তি করুন এবং প্রদত্ত অ্যারের মধ্যে শীর্ষ K সর্বাধিক ঘন ঘন উপাদানটি ফেরত দিন৷
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
bool compare(pair<int,int>&a, pair<int,int>&b){
return a.second>b.second;
}
void topKfrequent(int arr,int n, int k){
unordered_map<int,int>mp;
for(int i=0;i<n;i++){
mp[nums[i]]++;
}
vector<pair<int,int>>v(mp.begin(),mp.end());
sort(v.begin(),v.end(),compare);
for(int i=0;i<k;i++){
cout<<v[i].first<< " ";
}
}
int main(){
int N= 5;
int arr[N]= {1,1,3,2,2};
int k=2;
topKfrequent(arr,k);
return 0;
} আউটপুট
উপরের কোডটি চালানোর ফলে নিম্নলিখিত আউটপুট তৈরি হবে,
2 1
প্রদত্ত পূর্ণসংখ্যার বিন্যাসে, শীর্ষ K=2 সর্বাধিক ঘন ঘন উপাদানগুলি হল 2, 1৷
