मान लीजिए कि हमारे पास आकार N के पूर्णांकों की एक सरणी है। कार्य पूर्णांकों के दिए गए सरणी में मौजूद सबसे लगातार तत्व को खोजना है। उदाहरण के लिए,
इनपुट-1 -
N = 8
A[ ] = {1,2,4,3,3,1,1,5} आउटपुट -
1
स्पष्टीकरण - पूर्णांकों के दिए गए सरणी में, सबसे अधिक दिखाई देने वाली संख्या '1' है। इस प्रकार आउटपुट '1' है।
इनपुट-2 -
N = 6
A[ ] = {1,4,4,4,1,1} आउटपुट-ए -
1
आउटपुट-बी -
4
व्याख्या:पूर्णांकों के दिए गए सरणी में, सबसे अधिक दिखाई देने वाली संख्या '1' और '4' है। इस प्रकार हम उनमें से किसी एक को आउटपुट वापस कर सकते हैं।
इस समस्या को हल करने का तरीका
दिए गए सरणी में कई पूर्णांक होते हैं जिसमें हमें सरणी में मौजूद सबसे अधिक बार आने वाले तत्व को खोजना होता है। इस समस्या को रैखिक समय O(n) और रैखिक स्थान O(n) में हल करने के लिए, हम हैशमैप के दृष्टिकोण का उपयोग कर सकते हैं।
इस दृष्टिकोण में, हम एक अनियंत्रित नक्शा (एसटीएल लाइब्रेरी) बनाएंगे जिसमें की-वैल्यू पेयर होगा जिसमें कुंजी एक तत्व होगी और वैल्यू तत्व की घटना होगी। मानचित्र के माध्यम से यात्रा करते समय हम संख्या की अधिकतम आवृत्ति पाएंगे और संख्या को आउटपुट के रूप में वापस कर देंगे।
-
इनपुट आकार N की एक सरणी लें।
-
एक पूर्णांक फ़ंक्शन maxOccurrence(int A[], int size) एक इनपुट के रूप में एक सरणी और उसका आकार लेता है और अधिकतम आवृत्ति के साथ संख्या देता है।
-
कुंजी को एक तत्व और मान को इसकी आवृत्ति के रूप में लेकर सरणी के सभी तत्वों का हैशमैप बनाना।
-
मानचित्र पर पुनरावृत्ति करना और जाँच करना कि क्या किसी भी तत्व की आवृत्ति सबसे अधिक है, तो परिणाम को संख्या के रूप में वापस कर दें। अन्यथा, यदि सरणी में कोई संख्या मौजूद नहीं है तो '-1' लौटाएं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
int maxOccurrence(int A[], int size){
int mxcount=0;
int res=-1;
unordered_map<int,int>mp;
for(int i=0;i<size;i++){
mp[A[i]]++;
}
for(auto x:mp){
if(x.second>mxcount){
res= x.first;
mxcount=x.second;
}
}
return res;
}
int main(){
int N=6;
int A[N]= {1,4,4,4,2,1};
int ans= maxOccurrence(A,N);
cout<<ans<<endl;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाएंगे, तो यह आउटपुट को इस रूप में प्रिंट करेगा,
4
4 की आवृत्ति 3 है, जो दी गई सरणी में अन्य सभी संख्याओं से अधिकतम आवृत्ति है।