मान लीजिए हमारे पास एक ऐरे arr है। हम इंटीजर्स का एक सेट चुन सकते हैं और ऐरे में इन इंटीजर्स के सभी ऑकरेंसेज को हटा सकते हैं। हमें सेट का न्यूनतम आकार ढूंढना है ताकि ऐरे के कम से कम आधे इंटीजर्स हटा दिए जाएं। उदाहरण के लिए, अगर arr = [3,3,3,3,5,5,5,2,2,7], तो आउटपुट 2 होगा। ऐसा इसलिए क्योंकि अगर हम {3,7} चुनते हैं तो नया ऐरे [5,5,5,2,2] बनेगा जिसका साइज 5 है (यह पुराने ऐरे के साइज के आधे के बराबर है)। साइज 2 के संभावित सेट्स हैं {3,5},{3,2},{5,2}। सेट {2,7} चुनना संभव नहीं है क्योंकि यह नया ऐरे [3,3,3,3,5,5,5] बनाएगा जिसका साइज पुराने ऐरे के आधे से अधिक है।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
एक मैप m डिफाइन करें, n := arr का साइज, arr में मौजूद प्रत्येक एलिमेंट की फ्रीक्वेंसी को मैप m में स्टोर करें
temp नाम का एक ऐरे डिफाइन करें, sz := n, और ret := 0
m में प्रत्येक की-वैल्यू पेयर it के लिए:
it के वैल्यू को temp में इंसर्ट करें
temp ऐरे को सॉर्ट करें
i को 0 से temp के साइज तक लूप करें:
अगर sz <= n / 2, तो लूप से ब्रेक करें
ret को 1 से बढ़ाएं
sz को temp[i] से घटाएं
ret लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSetSize(vector<int>& arr) {
unordered_map <int, int> m;
int n = arr.size();
for(int i = 0; i < n; i++){
m[arr[i]]++;
}
vector <int> temp;
unordered_map <int, int> :: iterator it = m.begin();
int sz = n;
int ret = 0;
while(it != m.end()){
temp.push_back(it->second);
it++;
}
sort(temp.rbegin(), temp.rend());
for(int i = 0; i < temp.size(); i++){
if(sz <= n / 2)break;
ret++;
sz -= temp[i];
}
return ret;
}
};
int main(){
vector<int> v = {3,3,3,3,5,5,5,2,2,7};
Solution ob;
cout << (ob.minSetSize(v));
}
इनपुट
[3,3,3,3,5,5,5,2,2,7]
आउटपुट
2