在C ++中将数组大小减小一半

假设我们有一个数组arr。我们可以选择一组整数，并删除数组中所有这些整数的出现。我们必须找到集合的最小大小，以便删除数组的至少一半整数。因此，例如，如果arr = [3,3,3,3,5,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到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;
   }
};
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