力扣top100(day04-05)--堆
本文为力扣TOP100刷题笔记
笔者根据数据结构理论加上最近刷题整理了一套 数据结构理论加常用方法以下为该文章：
力扣外传之数据结构（一篇文章搞定数据结构）
215. 数组中的第K个最大元素
class Solution {// 快速选择递归函数int quickselect(int[] nums, int l, int r, int k) {if (l == r) return nums[k]; // 基准情况：区间只有一个元素// 选取基准值（这里简单选择最左边的元素）int x = nums[l], i = l - 1, j = r + 1;// 分区操作while (i < j) {// 从左找第一个大于等于x的元素do i++; while (nums[i] < x);// 从右找第一个小于等于x的元素do j--; while (nums[j] > x);// 交换这两个元素if (i < j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}// 递归处理包含第k元素的子区间if (k <= j) return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);}public int findKthLargest(int[] _nums, int k) {int n = _nums.length;// 将问题转化为找第n-k小的元素（即第k大的元素）return quickselect(_nums, 0, n - 1, n - k);}
}算法步骤
分区（Partition）：
选择一个基准值（pivot）
x（这里选择最左边的元素nums[l]）使用两个指针
i和j：
i从左向右找第一个≥x的元素
j从右向左找第一个≤x的元素交换这两个元素，直到
i和j相遇递归选择：
根据
k的位置决定递归处理左半部分还是右半部分如果
k在左半部分（k <= j），继续处理左半部分否则处理右半部分
转换问题：
第k大的元素 = 第(n-k)小的元素（
n - k）示例演示
假设输入数组为
[3,2,1,5,6,4]，k = 2（找第2大的元素）：
n = 6，转换为找第4小的元素（n - k = 4）初始调用
quickselect(nums, 0, 5, 4)分区过程：
基准值
x = 3
i找到5，j找到1交换后数组变为
[3,2,1,4,6,5]
j停在索引2因为
4 > 2，递归处理右半部分quickselect(nums, 3, 5, 4)再次分区：
基准值
x = 4
i找到6，j找到4交换后数组不变
j停在索引3因为
4 == 3，递归处理左半部分quickselect(nums, 3, 3, 4)直接返回
nums[4] = 5最终结果是5，即第2大的元素。
时间复杂度
平均情况：O(n)
最坏情况（每次选择的基准值都是最大或最小值）：O(n²)
347. 前 K 个高频元素
class Solution {public int[] topKFrequent(int[] nums, int k) {// 1. 使用哈希表统计每个数字出现的频率Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();for (int num : nums) {occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);}// 2. 创建最小堆，按照出现频率排序PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] m, int[] n) {return m[1] - n[1]; // 根据频率比较}});// 3. 遍历频率哈希表，维护大小为k的最小堆for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {// 如果当前元素的频率大于堆顶元素的频率if (queue.peek()[1] < count) {queue.poll(); // 移除堆顶最小频率元素queue.offer(new int[]{num, count}); // 加入当前元素}} else {queue.offer(new int[]{num, count});}}// 4. 从堆中提取结果int[] ret = new int[k];for (int i = 0; i < k; ++i) {ret[i] = queue.poll()[0]; // 取出数字部分}return ret;}
}算法步骤
统计频率：
使用哈希表
occurrences记录每个数字出现的次数遍历数组，对每个数字的计数加1
构建最小堆：
创建优先队列（最小堆），比较器基于频率（数组的第二个元素）
堆的大小限制为k，保持堆顶是当前k个元素中频率最小的
维护堆：
遍历频率哈希表
当堆未满时，直接加入元素
当堆已满时，比较当前元素频率与堆顶频率
如果当前频率更高，替换堆顶元素
否则跳过
提取结果：
从堆中依次取出元素，存入结果数组
注意：由于是最小堆，取出的顺序是从小到大，但不影响结果正确性
示例演示
假设输入
nums = [1,1,1,2,2,3]，k = 2：
统计频率：
occurrences = {1:3, 2:2, 3:1}构建堆过程：
加入1:3 →
[(1,3)]加入2:2 →
[(2,2), (1,3)]处理3:1时堆已满，3的频率1小于堆顶2的频率2，跳过
提取结果：
弹出(2,2)和(1,3)
结果
[2,1]（顺序不重要）时间复杂度分析
统计频率：O(n)，n为数组长度
建堆操作：O(m log k)，m为不同数字的个数
每个元素最多入堆一次，出堆一次
堆操作时间复杂度为O(log k)
总时间复杂度：O(n + m log k)
空间复杂度
哈希表：O(m)
堆：O(k)
总空间复杂度：O(m + k)
优化建议
当k接近m时：
可以直接排序频率哈希表，取前k个
时间复杂度O(m log m)
使用快速选择：
类似快速排序的分区思想
平均时间复杂度O(n)，但实现更复杂
并行处理：
对于大规模数据，可以并行统计频率
为什么使用最小堆？
最小堆能高效维护前k大的元素：
堆的大小限制为k，空间效率高
每次只需要比较堆顶元素，决定是否替换
插入和删除操作时间复杂度为O(log k)
这个实现很好地平衡了时间效率和代码简洁性，是解决Top K频率问题的经典方法。