【LeetCode Hot100 堆】第 K 大的元素、前 K 个高频元素

堆（Heap）数据结构

1. 什么是堆？

堆（Heap） 是一种 特殊的完全二叉树，满足以下性质：

• 任意节点的值 都满足 堆的性质（最大堆或最小堆）。
• 完全二叉树：除了最后一层，所有层都被填满，且最后一层的节点靠左排列。

两种常见类型

1. 最小堆（Min Heap）：父节点的值 小于等于 其子节点。
   • 堆顶元素 是最小值。
2. 最大堆（Max Heap）：父节点的值 大于等于 其子节点。
   • 堆顶元素 是最大值。

2. 堆的存储方式

堆通常使用 数组 存储，并且满足：

• 父节点：parent(i) = (i - 1) / 2
• 左子节点：left(i) = 2 * i + 1
• 右子节点：right(i) = 2 * i + 2

3. Java 中的堆（PriorityQueue）

Java 提供了 PriorityQueue 实现最小堆：

import java.util.PriorityQueue;

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 默认最小堆
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);

System.out.println(minHeap.poll()); // 输出 2（最小值）

如果要创建最大堆：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

第 K 大的元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

注意：

• 你需要找的是数组排序后的 第 k 个最大的元素，而不是第 k 个不同的元素。
• 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例

输入：

nums = [3,2,1,5,6,4], k = 2

输出：

5

使用堆求解第 K 大的元素

1. 方法概述

使用 最小堆（Min Heap） 可以高效地求解 第 K 大的元素，该方法的核心思想是维护一个大小为 k 的 最小堆，其中堆顶元素始终是当前 前 K 大元素 中的最小值。

2. 解题思路

1. 创建一个大小为 k 的最小堆（PriorityQueue）。
2. 遍历数组 nums：
   • 如果 堆的大小小于 k，则直接将当前元素 num 插入堆中。
   • 如果 堆的大小等于 k：
     • 只有当 num > 堆顶元素 时，才将堆顶元素移除，并插入 num。
3. 遍历结束后，堆顶元素即为第 k 大的元素。

3. 代码实现

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 创建一个最小堆（容量为 k）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        // 遍历数组
        for (int num : nums) {
            if (minHeap.size() < k) { 
                // 直接入堆
                minHeap.offer(num);
            } else if (num > minHeap.peek()) { 
                // 只在当前元素比堆顶元素大的时候进行替换
                minHeap.poll();
                minHeap.offer(num);
            }
        }
        // 堆顶即为第 k 大的元素
        return minHeap.peek();
    }
}

前 K 个高频元素

1. 题目描述

给定一个整数数组 nums 和一个整数 k，要求找出 出现频率最高的 K 个元素。返回顺序可以 任意。

2. 解题思路

1. 使用 HashMap 统计元素频率：遍历数组，记录每个数字的出现次数。
2. 构建最小堆（小根堆）：维护大小为 K 的最小堆，堆顶存储当前出现频率最低的元素。
3. 遍历 HashMap 并更新堆：
   • 若堆的大小小于 k，则直接加入堆。
   • 若新元素的频率 大于堆顶元素的频率，则替换堆顶元素并调整堆。
4. 堆中存储的即是前 K 个高频元素。

3. 代码实现

使用 PriorityQueue（Java 默认最小堆）

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // 2. 使用最小堆存储前 K 个高频元素
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int num = entry.getKey(), freq = entry.getValue();
            if (minHeap.size() < k) {
                minHeap.offer(new int[]{num, freq});
            } else if (freq > minHeap.peek()[1]) {
                minHeap.poll(); // 移除频率最小的
                minHeap.offer(new int[]{num, freq});
            }
        }

        // 3. 取出堆中的元素
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll()[0];
        }
        return result;
    }
}

Map.Entry<K, V> 介绍

• Map.Entry<K, V> 是 Java Map 接口的内部接口，表示 Map 中的 键值对（key-value）。
• entrySet() 方法返回 包含所有键值对 (Entry) 的集合，然后可以用 for-each 遍历。

entrySet() 作用

freqMap.entrySet() 返回一个 Set<Map.Entry<K, V>>，其中：

• 每个 Entry<K, V> 代表 一个键值对。
• getKey() 获取键（数字）。
• getValue() 获取值（出现的次数）。

Comparator.comparingInt(a -> a[1])

在 Java 中，Comparator.comparingInt(a -> a[1]) 用于创建一个 基于数组元素的某个索引值进行排序 的比较器，主要用于 PriorityQueue（优先队列） 或 Collections.sort()。
Comparator.comparingInt(a -> a[1])：

• comparingInt(ToIntFunction<T> keyExtractor)：Comparator 提供的 辅助方法，用于按照 int 类型的键排序。
• a -> a[1]：Lambda 表达式，指定对 a 这个数组的 索引 1 位置的值进行排序。