智能小程序搭建_免费直播软件下载_域名whois查询_谷歌优化排名哪家强

问题背景

给你一个整数数组 $arr$。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。

数据约束

• $1\le arr.length\le 10^5$
• $arr.length$ 为偶数
• $1\le arr[i]\le 105$

解题过程

去掉相同值最后考察数组大小，显然需要统计不同值出现的次数，要用到哈希表。
自己整了半天花活，最后发现不如直接排序。

具体实现

class Solution {public int minSetSize(int[] arr) {int max = 0;for(int item : arr) {max = Math.max(max, item);}int[] count = new int[max + 1];for(int item : arr) {count[item]++;}Arrays.sort(count);int target = arr.length >>> 1;for(int i = max; ; i--) {target -= count[i];if(target <= 0) {return max - i + 1;}}}
}