347-q.png
private class PairComparator implements Comparator<Pair<Integer, Integer>>{
@Override
public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2){
if(p1.getKey() != p2.getKey())
return p1.getKey() - p2.getKey();
return p1.getValue() - p2.getValue();
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
if(k <= 0)
throw new IllegalArgumentException("k should be greater than 0");
HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
for(int i = 0 ; i < nums.length ; i ++)
if(freq.containsKey(nums[i]))
freq.put(nums[i], freq.get(nums[i]) + 1);
else
freq.put(nums[i], 1);
if(k > freq.size())
throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");
PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<Pair<Integer, Integer>>(new PairComparator());
for(Integer num: freq.keySet()){
int numFreq = freq.get(num);
if(pq.size() == k){
if(numFreq > pq.peek().getKey()){
pq.poll();
pq.add(new Pair(numFreq, num));
}
}
else
pq.add(new Pair(numFreq, num));
}
ArrayList<Integer> res = new ArrayList<Integer>();
while(!pq.isEmpty())
res.add(pq.poll().getValue());
return res;
}
