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 <= 0)
throw new IllegalArgumentException("k should be greater than 0");
// 统计æ¯ä¸ªå…ƒç´ 出现的频率
HashMap freq = new HashMap<>();
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");
// 扫æ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);
}
}