【leetcode】前 K 个高频元素
题目：
给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。
思路：
求频率最高的题目， 第一想法就是要用HashMap，key是每个数字，value是数字出现的次数。
求出每个数字的频率之后，我们想要求出第k高的频率的元素，并且时间复杂度必须优于O(nlog n)，那么该如何求呢？
我们应该想到，堆的时间复杂度正好是O(nlog n)，可以用堆来求。而堆是可以利用优先队列PriorityQueue来求的。
重写compare方法，把频率最高的前k个数字加入queue中， 最后只要把优先队列中的值给弹出，然后再add到list中去就可以了。
java代码：
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
Map<Integer, Integer> map = new HashMap();
for (int i : nums) {
if (!map.containsKey(i)) {
map.put(i, 1);
} else {
map.put(i, map.get(i) + 1);
}
}
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1) - map.get(o2);
}
});
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (queue.size() < k) {
queue.add(entry.getKey());
} else {
if (entry.getValue() > map.get(queue.peek())) {
queue.remove();
queue.add(entry.getKey());
}
}
}
while (!queue.isEmpty()) {
res.add(queue.remove());
}
return res;
}
}
