本文为力扣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);}
}

算法步骤

1. 分区（Partition）：

   • 选择一个基准值（pivot）x（这里选择最左边的元素nums[l]）

   • 使用两个指针i和j：

     • i从左向右找第一个≥x的元素

     • j从右向左找第一个≤x的元素

     • 交换这两个元素，直到i和j相遇

2. 递归选择：

   • 根据k的位置决定递归处理左半部分还是右半部分

   • 如果k在左半部分（k <= j），继续处理左半部分

   • 否则处理右半部分

3. 转换问题：

   • 第k大的元素 = 第(n-k)小的元素（n - k）

示例演示

假设输入数组为[3,2,1,5,6,4]，k = 2（找第2大的元素）：

1. n = 6，转换为找第4小的元素（n - k = 4）

2. 初始调用quickselect(nums, 0, 5, 4)

3. 分区过程：

   • 基准值x = 3

   • i找到5，j找到1

   • 交换后数组变为[3,2,1,4,6,5]

   • j停在索引2

4. 因为4 > 2，递归处理右半部分quickselect(nums, 3, 5, 4)

5. 再次分区：

   • 基准值x = 4

   • i找到6，j找到4

   • 交换后数组不变

   • j停在索引3

6. 因为4 == 3，递归处理左半部分quickselect(nums, 3, 3, 4)

7. 直接返回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;}
}

算法步骤

1. 统计频率：

   • 使用哈希表occurrences记录每个数字出现的次数

   • 遍历数组，对每个数字的计数加1

2. 构建最小堆：

   • 创建优先队列（最小堆），比较器基于频率（数组的第二个元素）

   • 堆的大小限制为k，保持堆顶是当前k个元素中频率最小的

3. 维护堆：

   • 遍历频率哈希表

   • 当堆未满时，直接加入元素

   • 当堆已满时，比较当前元素频率与堆顶频率

     • 如果当前频率更高，替换堆顶元素

     • 否则跳过

4. 提取结果：

   • 从堆中依次取出元素，存入结果数组

   • 注意：由于是最小堆，取出的顺序是从小到大，但不影响结果正确性

示例演示

假设输入nums = [1,1,1,2,2,3]，k = 2：

1. 统计频率：

   • occurrences = {1:3, 2:2, 3:1}

2. 构建堆过程：

   • 加入1:3 → [(1,3)]

   • 加入2:2 → [(2,2), (1,3)]

   • 处理3:1时堆已满，3的频率1小于堆顶2的频率2，跳过

3. 提取结果：

   • 弹出(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)

优化建议

1. 当k接近m时：

   • 可以直接排序频率哈希表，取前k个

   • 时间复杂度O(m log m)

2. 使用快速选择：

   • 类似快速排序的分区思想

   • 平均时间复杂度O(n)，但实现更复杂

3. 并行处理：

   • 对于大规模数据，可以并行统计频率

为什么使用最小堆？

最小堆能高效维护前k大的元素：

1. 堆的大小限制为k，空间效率高

2. 每次只需要比较堆顶元素，决定是否替换

3. 插入和删除操作时间复杂度为O(log k)

这个实现很好地平衡了时间效率和代码简洁性，是解决Top K频率问题的经典方法。