मान लीजिए कि हमारे पास आकार 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 सबसे लगातार तत्वों का आउटपुट परिणाम लौटाएँ।
-
एन को इनपुट के रूप में और एन तत्वों की सरणी लें।
-
एक फ़ंक्शन 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 हैं।