数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中将数组大小减半
假设我们有一个数组 arr。我们可以选择一组整数并删除数组中这些整数的所有出现。我们必须找到集合的最小大小，以便删除数组中至少一半的整数。例如，如果 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 中的每个键值对 it
将 it 的值插入到 temp 中
对 temp 数组进行排序
对于 I 从 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
更新于: 2020-04-29
1K+ 浏览量
广告