C++ এ অ্যারের আকার অর্ধেক কমিয়ে দিন

ধরুন আমাদের একটি অ্যারে অ্যারে আছে। আমরা পূর্ণসংখ্যার একটি সেট বেছে নিতে পারি এবং অ্যারেতে এই পূর্ণসংখ্যাগুলির সমস্ত উপস্থিতি মুছে ফেলতে পারি। আমাদের সেটের সর্বনিম্ন আকার খুঁজে বের করতে হবে যাতে অ্যারের অন্তত অর্ধেক পূর্ণসংখ্যা সরানো হয়। সুতরাং উদাহরণস্বরূপ, যদি 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

  -এ যুক্ত করুন

  • temp

    এ এর ​​মান সন্নিবেশ করান

• টেম্প অ্যারে সাজান

• আমি 0 থেকে টেম্পের আকারের মধ্যে

  • যদি sz <=n / 2, তাহলে লুপ থেকে বিরতি

  • 1 দ্বারা ret বাড়ান

  • temp[i]

    দ্বারা sz হ্রাস করুন

• রিটার্ন রিটার্ন

উদাহরণ (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