知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 数组中的第K个最大元素 ## 题目(LeetCode 215) 在未排序的数组中找到第 k 个最大的元素。 ``` 输入:[3,2,1,5,6,4], k = 2 输出:5 ``` ## 解法一:快速选择(最优) ```java class Solution { public int findKthLargest(int[] nums, int k) { int target = nums.length - k; // 第k大 = 排序后下标 n-k return quickSelect(nums, 0, nums.length - 1, target); } private int quickSelect(int[] nums, int lo, int hi, int target) { int pivot = partition(nums, lo, hi); if (pivot == target) return nums[pivot]; else if (pivot < target) return quickSelect(nums, pivot + 1, hi, target); else return quickSelect(nums, lo, pivot - 1, target); } private int partition(int[] nums, int lo, int hi) { // 随机选 pivot 避免最坏情况 int rand = lo + new Random().nextInt(hi - lo + 1); swap(nums, rand, hi); int pivot = nums[hi], i = lo; for (int j = lo; j < hi; j++) { if (nums[j] <= pivot) { swap(nums, i++, j); } } swap(nums, i, hi); return i; } private void swap(int[] nums, int a, int b) { int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; } } ``` ## 解法二:小顶堆 ```java class Solution { public int findKthLargest(int[] nums, int k) { int heapSize = nums.length; buildMaxHeap(nums, heapSize); for (int i = nums.length - 1; i >= nums.length - k + 1; --i) { swap(nums, 0, i); --heapSize; maxHeapify(nums, 0, heapSize); } } ``` > 💬 **Q:解释这段堆排序代码的逻辑,给出示例** > > 思路:建大顶堆 → 把堆顶(最大值)换到末尾 → 做 k-1 次 → 堆顶就是第 k 大。 > > 三个方法的职责: > - `buildMaxHeap`:从最后一个非叶子节点(`heapSize/2-1`)开始,自底向上调用 maxHeapify,建好大顶堆 > - `maxHeapify`:比较当前节点和左右子节点,把最大的换上来,递归向下调整("下沉"操作) > - `findKthLargest`:建堆后循环 k-1 次,每次把堆顶换到末尾并缩小堆,最后堆顶就是答案 > > 用 `nums = [3,2,1,5,6,4], k=2` 模拟: > > ``` > 第一步:buildMaxHeap > > 原数组:[3, 2, 1, 5, 6, 4] 树形: 3 > / \ > 2 1 > / \ / > 5 6 4 > > i=2: 节点1 vs 左子4 → 交换 → [3,2,4,5,6,1] > i=1: 节点2 vs 左子5,右子6 → 6最大,交换 → [3,6,4,5,2,1] > i=0: 节点3 vs 左子6,右子4 → 6最大,交换 → [6,3,4,5,2,1] > 递归下沉:3 vs 左子5,右子2 → 5最大,交换 → [6,5,4,3,2,1] > > 大顶堆建好:[6, 5, 4, 3, 2, 1] > > 第二步:循环 k-1=1 次 > > i=5: swap(0,5) → [1,5,4,3,2, |6] ← 最大值6归位到末尾 > heapSize=5, maxHeapify(0): > 1 vs 5,4 → 5最大 → [5,1,4,3,2, |6] > 1 vs 3,2 → 3最大 → [5,3,4,1,2, |6] > > 循环结束,nums[0] = 5 = 第2大 ✓ > ``` > > 为什么循环 k-1 次而不是 k 次?每次把当前最大值移走,做 k-1 次后前 k-1 大都移走了,堆顶自然是第 k 大。 > 💬 **Q:给出源码实现(不用 PriorityQueue,手动实现小顶堆)**i >= 0; --i) { maxHeapify(a, i, heapSize); } } public void maxHeapify(int[] a, int i, int heapSize) { int l = i * 2 + 1, r = i * 2 + 2, largest = i; if (l < heapSize && a[l] > a[largest]) { largest = l; } if (r < heapSize && a[r] > a[largest]) { largest = r; } if (largest != i) { swap(a, i, largest); maxHeapify(a, largest, heapSize); } } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } ``` > 💬 **Q:给出源码实现(不用 PriorityQueue,手动实现小顶堆)** > > 小顶堆的本质是一个数组,满足:`arr[i] <= arr[2i+1]` 且 `arr[i] <= arr[2i+2]`(父节点 ≤ 子节点)。 > > 核心操作只有两个:**上浮**(插入时)和**下沉**(删除堆顶时)。 > > > 堆的数组下标关系: > ``` > 父节点 index → 左子节点 2*index+1,右子节点 2*index+2 > 子节点 index → 父节点 (index-1)/2 > ``` > > 这就是 `PriorityQueue` 内部的核心逻辑,JDK 源码里的 `siftUp` 和 `siftDown` 方法名字都一样。 ## 复杂度 - 快速选择:平均 O(n),最坏 O(n²),空间 O(1) - 小顶堆:O(n log k),空间 O(k) ## 一句话总结 快速选择只处理目标所在的那一半,平均线性时间;堆解法更稳定但多个 log 因子。 --- 下一篇:[05 - K个一组翻转链表](./05-reverse-k-group.md) ## 解法对比 | | 解法一(快速选择) | 解法二(小顶堆) | |--|--------|--------| | 时间复杂度 | 平均 O(n),最坏 O(n²) | O(n log k) | | 空间复杂度 | O(1) | O(k) | | 特点 | 平均最快,会修改原数组 | 稳定,适合数据流场景 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入