在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，则从循环中断
增加ret1
将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