C++で配列サイズを半分に減らします

これを解決するには、次の手順に従います-

• マップm、n：=arrのサイズを定義し、arrに存在する各要素の頻度をマップmに格納します

• temp、sz：=n、およびret：=0と呼ばれる配列を定義します

• キーと値のペアごとに、m

  で

  • その値をtempに挿入します

• 一時配列を並べ替える

• 0からtempのサイズまでの範囲のIの場合

  • 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;
   }
};
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