Reduce Array Size to The Half
给一个数组, 问去除中间几个数(包括重复的), 能让size变成至少一半. 先统计一下, 然后用pq一个个算.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public int minSetSize(int[] arr) { Map<Integer, Integer> count = new HashMap<>(); PriorityQueue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() { @Override public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) { return o2.getValue() - o1.getValue(); } }); for(int n : arr) count.put(n, count.getOrDefault(n , 0) + 1); for (Map.Entry<Integer, Integer> e : count.entrySet()) q.add(e); int target = arr.length / 2; int sum = 0; int c = 0; while(sum < target) { sum += q.poll().getValue(); c++; } return c; } } |