-
Notifications
You must be signed in to change notification settings - Fork 0
/
TopK.java
34 lines (32 loc) · 1.14 KB
/
TopK.java
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
class TopK {
public int[] topKFrequent(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) return nums;
Map<Integer, Integer> freqMap = buildMap(nums);
PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(new MyComparator());
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
minHeap.offer(entry);
if (minHeap.size() > k) {
minHeap.poll();
}
}
int[] res = new int[k];
int i = 0;
while (!minHeap.isEmpty()) {
res[i++] = minHeap.poll().getKey();
}
return res;
}
static class MyComparator implements Comparator<Map.Entry<Integer, Integer>> {
@Override
public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
return Integer.compare(e1.getValue(), e2.getValue());
}
}
private Map<Integer, Integer> buildMap(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
return map;
}
}