网站建设服务费账务处理,笑话小网站模板html,品牌网站制作价格,网站前置审批证书1. 题目
给你一个整数数组 arr。你可以从中选出一个整数集合#xff0c;并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。
示例 1#xff1a;
输入#xff1a;arr [3,3,3,3,5,5,5,2,2,7]
输出#xff1a;2
解释#xff1a…1. 题目
给你一个整数数组 arr。你可以从中选出一个整数集合并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。
示例 1
输入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]新数组长度大于原数组的二分之一。示例 2
输入arr [7,7,7,7,7,7]
输出1
解释我们只能选择集合 {7}结果数组为空。示例 3
输入arr [1,9]
输出1示例 4
输入arr [1000,1000,3,7]
输出1示例 5
输入arr [1,2,3,4,5,6,7,8,9,10]
输出5提示
1 arr.length 10^5
arr.length 为偶数
1 arr[i] 10^5来源力扣LeetCode 链接https://leetcode-cn.com/problems/reduce-array-size-to-the-half 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:int minSetSize(vectorint arr) {mapint,int m;for(auto a : arr)m[a];//统计个数priority_queueint q;//默认大顶堆for(auto it : m)q.push(it.second);//个数int target arr.size()/2, count 0, n 0;while(count target){count q.top();n;q.pop();}return n;}
};
