सी++ में ऐरे साइज को आधा कर दें

मान लीजिए कि हमारे पास एक सरणी गिरफ्तारी है। हम पूर्णांकों का एक सेट चुन सकते हैं और सरणी में इन पूर्णांकों की सभी घटनाओं को हटा सकते हैं। हमें समुच्चय का न्यूनतम आकार ज्ञात करना है ताकि सरणी के कम से कम आधे पूर्णांकों को हटा दिया जाए। तो उदाहरण के लिए, अगर 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 में संग्रहीत करें

• एक सरणी को परिभाषित करें जिसे अस्थायी कहा जाता है, sz:=n, और ret:=0

• प्रत्येक की-वैल्यू पेयर के लिए इसे m

  . में जोड़ें

  • इसका मान अस्थायी में डालें

• अस्थायी सरणी क्रमबद्ध करें

• मैं के लिए 0 से लेकर अस्थायी के आकार तक

  • अगर sz <=n / 2, तो लूप से ब्रेक करें

  • रिट को 1 से बढ़ाएं

  • तापमान से sz घटाएं[i]

• वापसी रिट

उदाहरण (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;
   }
};
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