LeetCode 347.前 K 个高频元素
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
Java 实现代码
class Solution {public int[] topKFrequent(int[] nums, int k) {// 统计每个元素的频率Map<Integer, Integer> freqMap = new HashMap<>();for (int num : nums) {freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);}// 使用一个最小堆（优先队列）来存储频率前 k 大的元素PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());// 保持堆的大小为 kfor (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {minHeap.offer(entry);if (minHeap.size() > k) {minHeap.poll(); // 移除堆顶元素}}// 提取堆中的元素，得到结果int[] result = new int[k];int index = 0;while (!minHeap.isEmpty()) {result[index++] = minHeap.poll().getKey();}return result;}
}
解题思路
统计元素频率 首先，我们需要统计数组中每个元素的出现频率。我们可以使用一个哈希表（
Map<Integer, Integer>）来记录每个元素及其频率。使用最小堆 为了高效地找到前
k个高频元素，我们可以使用一个最小堆（PriorityQueue）。
- 插入元素时，堆中的大小会保持为
k，若堆中的元素超过k个，则移除堆顶元素（即当前频率最小的元素）。- 通过最小堆的性质，最终堆顶元素就是频率最小的那一个。
返回结果 最后，将堆中的元素提取出来，得到前
k个高频元素。
复杂度分析
- 时间复杂度：
O(n log k)。- 空间复杂度：
O(n + k)
