学习目标：

每天睡前是否感到浑浑噩噩，一天又在不知不觉中过去，回想我今天都干了什么呢？

啊~我这一天又什么也没干，好有罪恶感啊，不行，我明天一定要好好学算法（手动狗头）。

明日复明日，明日何其多？不要等明天啦，和小编一起，每天睡前一道算法题，不仅解决你一天的空虚，更能助你安心入眠，远离熬夜。还能学到一点算法知识。不要小看这些知识哦，不积跬步无以至千里，不积小流无以成江海。每位大佬都不是一夜成名，都是从小白做起，日积月累，终成大佬，和小编一起，每日一题，走向大佬之路吧！

---

学习内容：

我们的题基本都是一些较为基础，适合日（睡）常（前）看的题，不会让你一眼就看出答案，是稍稍一点脚就能摸到头绪，但是在想的过程中又一时不知如何实现，再一想，又柳暗花明，最终跟着小编的思路一起解决问题，有不同思路可以发在评论区，一起讨论。“你若在，我必回”。

---

今天的题目是一道简单的排序+贪心的问题。直接看题目：

给你一个整数数组 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

 我们之前对于贪心已经有了初步的介绍，还不懂的朋友可以看下贪心简介https://blog.csdn.net/Cooler_z/article/details/122364926?spm=1001.2014.3001.5502

 关于本题，要求是让我们删除数组中的全部某个数，在删除次数最小的条件下让数组剩余数不大于原来的一半，返回最少次数。

根据我们的贪心思想，一定是依次删除这个数组出现次数最多的那个数，也就是众数。

接下来就是如何处理了。如何寻找众数，方法有很多，小编的方法是先进行桶排序，然后将每个不为0的数存入动态数组p中，因为我们对数字的值不是很关心，所以我们只要知道数的种类和个数即可。然后将数组p由大到小排序，然后我们只要从p的第一个开始加，直到总和大于等于n/2。有不同想法欢迎在评论区留言讨论，共同进步。

下面看看代码如何实现：

注意关于sort函数如何由大到小排序。

class Solution {
public:int minSetSize(vector<int>& arr) {int n=arr.size(),ans=0,sum=0,i;vector<int> p,num(100001,0);for(i=0;i<n;i++) num[arr[i]]++;for(i=0;i<100001;i++){if(num[i]!=0) p.push_back(num[i]);}sort(p.rbegin(),p.rend());n/=2,i=0;while(ans<n && i<p.size()){ans+=p[i++];sum++;}return sum;}
};

每天坚持是一件很累的事，即使很慢，但也不要停止。由于过年，小编停更了几天，从今天开始，小编继续每日一题。欢迎大家及时督促，大家一起加油！ 

---

大家记得点赞收藏，防止找不到哦。

欢迎大家订阅小编的每日一题专栏，会每天更新，都是用心准备的哦！

若有不同思路，欢迎评论区留言，看到必回，Goodnight！