题目地址
https://leetcode-cn.com/problems/top-k-frequent-elements/
题目描述
给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。
思路
- 记录每个元素出现的次数。
- 将所有元素按次数加进由优先队列实现的小根堆（频次最少的在最上面），只加K个元素即可，最后返回小根堆里的元素。
PS：可以温习下不由Java API怎么实现大小根堆。
解答
/**
* 执行用时：18 ms, 在所有 Java 提交中击败了27.28%的用户
* 内存消耗：41.1 MB, 在所有 Java 提交中击败了42.09%的用户
* @Author: vividzcs
* @Date: 2021/2/8 8:25 下午
*/
public class TopKFrequent {
public static void main(String[] args) {
int[] nums = {1,1,1,2,2,3,3,3,3};
int k = 2;
int[] result = topKFrequent(nums, k);
for (int item : result) {
System.out.print(item + " ");
}
System.out.println();
}
private static int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> record = new HashMap<>();
for (int i=0; i<nums.length; i++) {
if (record.containsKey(nums[i])) {
record.put(nums[i], record.get(nums[i]) + 1);
} else {
record.put(nums[i], 1);
}
}
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return record.get(o1) - record.get(o2);
}
});
for (Integer item : record.keySet()) {
if (queue.size() < k) {
queue.add(item);
} else if (record.get(item) > record.get(queue.peek())) {
queue.remove();
queue.add(item);
}
}
int[] result = new int[k];
for (int i=0; i<result.length; i++) {
result[i] = queue.remove();
}
return result;
}
}
