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

堆

• 堆（Heap）数据结构
• • 1. 什么是堆？
  • • 两种常见类型
  • 2. 堆的存储方式
  • 3. Java 中的堆（PriorityQueue）
• 第 K 大的元素
• • 题目描述
  • 示例
  • 使用堆求解第 K 大的元素
  • • 1. 方法概述
    • 2. 解题思路
    • 3. 代码实现
• 前 K 个高频元素
• • 1. 题目描述
  • 2. 解题思路
  • 3. 代码实现
  • • 使用 `PriorityQueue`（Java 默认最小堆）
    • Map.Entry 介绍
    • entrySet() 作用
    • Comparator.comparingInt(a -> a[1])

堆（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 介绍

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

entrySet() 作用

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

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

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

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

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