GitHub Viewer
package LeetCode;
import javafx.util.Pair;
import java.util.*;
public class LeetCode347 {
// 347. Top K Frequent Elements
// https://leetcode.com/problems/top-k-frequent-elements/description/
// 时间复杂度: O(nlogk)
// 空间复杂度: O(n + k)
private class PairComparator implements Comparator {
@Override
public int compare(Pair p1, Pair p2){
if(p1.getKey() != p2.getKey())
return p1.getKey() - p2.getKey();
return p1.getValue() - p2.getValue();
}
}
// nums = [1,1,1,2,2,3], k = 2
public List topKFrequent(int[] nums, int k) {
if(k freq.size())
throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");
// 扫描freq,维护当前出现频率最高的k个元素
// 在优先队列中,按照频率排序,所以数据对是 (频率,元素) 的形式
// 这里的是最小队列
PriorityQueue pq = new PriorityQueue(new PairComparator());
for(Integer num: freq.keySet()){
int numFreq = freq.get(num);
// 维护k个值，当前元素比优先队列出现的频率要高，那就出队！
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 res = new ArrayList();
while(!pq.isEmpty())
res.add(pq.poll().getValue());
return res;
}
public static void main(String[] args) {
int[] nums = {1, 1, 1, 2, 2, 3};
new LeetCode347().topKFrequent(nums, 2);
}
}