LeetCode 1338. Reduce Array Size to the half

, , , ,

Question

Given an array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

Example

1
2
3
4
5
6
7
8
9
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array

Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.

Solution

Sorting and then delete the number which with maximum frequency.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// time:O(nlogn) space:O(n)
    public int minSetSize(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        HashMap<Integer, Integer> map  = new HashMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int n = arr.length;
        int half = n / 2;
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        pq.addAll(map.entrySet());
        int res = 0;
        while (!pq.isEmpty()) {
            Map.Entry<Integer, Integer> curr = pq.poll();
            res++;
            n -= curr.getValue();
            if (n <= half) break;
        }
        return res;
    }
// Counting sort
// time:O(n) space:O(n)
    public int minSetSize2(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        HashMap<Integer, Integer> map  = new HashMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer>[] list = new ArrayList[arr.length + 1];
        for (int key : map.keySet()) {
            int count = map.get(key);
            if (list[count] == null) {
                list[count] = new ArrayList<Integer>();
            }
            list[count].add(key);
        }
        int res = 0;
        int count = 0;
        int n = arr.length;
        for (int i = arr.length; i >= 0; i--) {
            if (list[i] != null) {
                for (int num : list[i]) {
                    res++;
                    count += i;
                    if (count >= n / 2) return res;
                }
            }
        }
        return n;
    }

Reference