LeetCode：前K个高频元素【347】
题目描述
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目分析
我们还是基于优先队列或者说是小顶堆来AC这个题目。这道题是数组中的第K个最大元素【215】的进阶版。
我们在215题中说了，优先队列的排序规则是基于比较器或者自然顺序的，这道题就是基于比较器的。至于为什么可以用堆来实现，请查看215的题解，此处不在赘述。
首先我们堆的每个节点保存了两个信息（数值，频率），并且存在对应关系，所以我们可以使用Map(Key,Value)来存储节点信息。
Map<Integer,Integer> countMap = new HashMap<>();
for(int num:nums)
countMap.put(num,countMap.getOrDefault(num,0)+1);
然后，优先队列的比较器应该是基于频率的，也就是Map中的Value：
new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return countMap.get(o1).compareTo(countMap.get(o2));
}
}
基于这样的比较器，我们就可以建立一个根据频度从小打大的小顶堆。翻看了别人的代码后，我发现可以用Lambda表达式来简写比较规则
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,Comparator.comparingInt(num -> countMap.get(num)));
这样一句话就指明了，比较器的比较规则，Lambda表达式果然很神奇。但是使用了Lambda表达式后效率明显下降了，我也不太懂Lambda表达式，让我们继续努力吧：
Java题解
import java.util.*;
public class TopKFrequentElements_347 {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer,Integer> countMap = new HashMap<>();
for(int num:nums)
countMap.put(num,countMap.getOrDefault(num,0)+1);
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,Comparator.comparingInt(num -> countMap.get(num)));
for (int num : countMap.keySet()) {
priorityQueue.offer(num);
if (priorityQueue.size() > k) {
priorityQueue.poll();
}
}
return new ArrayList<>(priorityQueue);
}
public List<Integer> topKFrequent1(int[] nums, int k) {
Map<Integer,Integer> countMap = new HashMap<>();
for(int num:nums)
countMap.put(num,countMap.getOrDefault(num,0)+1);
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return countMap.get(o1).compareTo(countMap.get(o2));
}
});
for (int num : countMap.keySet()) {
priorityQueue.offer(num);
if (priorityQueue.size() > k) {
priorityQueue.poll();
}
}
return new ArrayList<>(priorityQueue);
}
}