1338. Reduce Array Size to The Half

 一刷 08/2022

Version #1 HashMap + sorting

Time - N is array length, create the hash map O(N), sort the count worst case O(NlogN) - total O(NlogN)

Space - O(N)

Runtime: 63 ms, faster than 75.56% of Java online submissions for Reduce Array Size to The Half.

Memory Usage: 84.5 MB, less than 65.96% of Java online submissions for Reduce Array Size to The Half.

class Solution {

    public int minSetSize(int[] arr) {

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

        for (int num : arr) {

            map.put(num, map.getOrDefault(num, 0) + 1);

        }

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

        Collections.sort(counts, Collections.reverseOrder());

        // 0 1

        int want = arr.length / 2 + arr.length % 2;

        int i = 0;

        while (want > 0) {

            want -= counts.get(i++);

        }

        return i;

    }

}