मान लीजिए हमारे पास आकार 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[arr[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, N, k);
return 0;
}
आउटपुट
उपरोक्त कोड चलाने पर निम्न आउटपुट उत्पन्न होगा,
2 1
दी गई पूर्णांकों की सरणी में, शीर्ष K=2 सबसे बारंबार तत्व 2, 1 हैं।
