मान लीजिए हमारे पास आकार 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) में हल करने के लिए, हम हैशमैप के दृष्टिकोण का उपयोग कर सकते हैं।
इस दृष्टिकोण में, हम एक अनऑर्डर्ड मैप (STL लाइब्रेरी) बनाएंगे जिसमें कुंजी-वैल्यू जोड़ी होगी जिसमें कुंजी एक तत्व होगी और वैल्यू तत्व की घटना होगी। मैप के माध्यम से पार करते समय हम नंबर की अधिकतम घटना ढूंढेंगे और नंबर को आउटपुट के रूप में लौटाएंगे।
आकार 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 है, जो दी गई सरणी में अन्य सभी नंबरों से अधिकतम बारंबारता है।
