【贪心】数组大小减半

、

/** 贪心：对所有数字出现的次数进行降序排序，并对这些次数相加，
 *        一旦相加结果大于等于arr数组长度的一半就返回结果。
 *
 * @auther start
 * @create 2024-01-16 10:20
 */
public class L1338 {
    public int minSetSize(int[] arr) {
        //使用哈希表报存每个数出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            //getOrDefault()方法表示如果存在key值就返回对应的value值，如果不存在key值
            //就返回自己设置的value值。
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //转换为list集合，对value值进行排序
        List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
        //使用lamda语法进行排序，降序排序
        Collections.sort(list,(o1,o2) -> o2.getValue().compareTo(o1.getValue()));
        int ans = 0, sums = 0;
        //遍历每个数出现的次数
        for (Map.Entry<Integer,Integer> li : list) {
            ans++;
            sums += li.getValue();
            if (sums >= arr.length/2)
                break;
        }
        return ans;
    }
}