前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

解题思路

• 1、使用哈希表来统计数组中每个元素的出现频率。
• 2、使用最小堆（MinHeap）来找到出现频率前k高的元素。
• 3、遍历哈希表中的每个元素，将元素和其频率插入最小堆中：

•  如果堆的大小小于k，将当前元素插入堆中；
  

•  如果堆的大小已经达到k，且当前元素的频率大于堆顶元素的频率，则弹出堆顶元素并将当前元素插入堆中。
  

• 4、最终堆中的元素即为出现频率前k高的元素。

Java实现

public class TopKFrequentElements {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<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(freqMap::get));for (int num : freqMap.keySet()) {minHeap.offer(num);if (minHeap.size() > k) {minHeap.poll();}}// 将堆中的元素转换为数组返回int[] result = new int[k];for (int i = k - 1; i >= 0; i--) {result[i] = minHeap.poll();}return result;}public static void main(String[] args) {TopKFrequentElements solution = new TopKFrequentElements();int[] nums = {1, 2, 1, 2, 4, 3,3,1,4,2,1};int k = 2;int[] topKElements = solution.topKFrequent(nums, k);System.out.println("Top " + k + " frequent elements: " + Arrays.toString(topKElements)); // Output: [1, 2]}
}

时间空间复杂度

时间复杂度：统计频率的时间复杂度为O(n)，构建最小堆的时间复杂度为O(k log k)，总时间复杂度为O(n + k log k)。（k->n时，时间复杂度O(nlogn）)

空间复杂度：哈希表和最小堆各需要O(n)的额外空间。