# Java Solution. Use HashMap and PriorityQueue

• ``````public class Solution {
// supply a new implementation for Map.Entry Comparator
class EntryComparator<K, V extends Comparable<V>>
implements Comparator<Map.Entry<?, V>> {
public int compare(Map.Entry<?, V> left, Map.Entry<?, V> right) {
// Call compareTo() on V, which is known to be a Comparable<V>
return right.getValue().compareTo(left.getValue());
}
}

public List<Integer> topKFrequent(int[] nums, int k) {
// Priority Queue's size is k, hence the run time for this case is just O(lgK).
PriorityQueue<Map.Entry<Integer, Integer>> kFrequent = new PriorityQueue<>(k,
// override Comprator class
new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(Map.Entry<Integer, Integer> left, Map.Entry<Integer, Integer>right){
return right.getValue().compareTo(left.getValue());
}
}
);
HashMap<Integer, Integer> map = new HashMap<>();
for(int i : nums){
map.putIfAbsent(num, 0);
// if key is already in the map, then increase the counter
map.computeIfPresent(num, (key, oldVal) -> oldVal + 1);
}
//use priority queue to find kFrequent
for(Map.Entry<Integer, Integer> mapEntry : map.entrySet()){
kFrequent.offer(mapEntry);
}
List<Integer> returnList = new ArrayList<>();
for(int i = 0; i < k; i++){
// in practice, we need check operation is null or not
//System.out.println(kFrequent.poll());
}
return returnList;
}
}``````

• @zhexuany This is O(nlgn), not the O(nlgk) because you added all the map entry to the queue. The first argument in PriorityQueue constructor is just init capacity.

``````for(Map.Entry<Integer, Integer> mapEntry : map.entrySet()){
if (kFrequent.size() == k && kFrequent.peek().getValue < mapEntry.getValue()) kFrequent.poll();
if (kFrequent.size() < k) kFrequent.offer(mapEntry);
}
``````

And to make this work you will need to change the PriorityQueue a Min-Heap by changing the comparator:

``````PriorityQueue<Map.Entry<Integer, Integer>> kFrequent = new PriorityQueue<>(k, new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(Map.Entry<Integer, Integer> left, Map.Entry<Integer, Integer>right) {
return left.getValue().compareTo(right.getValue());
}
});

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.