hashmpa 贪心算法

https://leetcode-cn.com/problems/reduce-array-size-to-the-half/solution/java-hashmappai-xu-tan-xin-by-gfu/

 

思路

利用HashMap统计arr数组中各个数值出现的次数，其中key = 数值, value = 出现次数。

统计结束后将HashMap中所有value(即出现次数)添加到ArrayList中。

随后根据出现次数，将利用Collections.sort()根据value(即出现次数)降序排序。

将数组原始长度的一半记为limit，将数组原始长度记为len，用其减去当前最大的出现次数，判断len是否< limit。

 

代码

class Solution {

    public int minSetSize(int[] arr) {

        int len = arr.length, res = 0, limit = len >> 1;

        HashMap<Integer, Integer> map = new HashMap<>(len);

        for (int num : arr)

            map.merge(num, 1, (o_val, n_val) -> o_val + n_val);

        ArrayList<Integer> list = new ArrayList<>(map.values());

        Collections.sort(list, Comparator.comparingInt(item -> -item));

        for (int num : list) {

            ++res;

            if ((len -= num) <= limit)

                return res;

        }

        return -1;

    }

}

代码(stream写法)

PS:对于小数据量而言，使用stream会很慢

 

class Solution {

    public int minSetSize(int[] arr) {

        int len = arr.length, res = 0, limit = len >> 1;

        Map<Integer, Long> map = Arrays.stream(arr).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        ArrayList<Long> list = new ArrayList<>(map.values());

        Collections.sort(list, Comparator.comparingLong(item -> -item));

        for (long num : list) {

            ++res;

            if ((len -= num) <= limit)

                return res;

        }

        return -1;

    }

}