Leetcode215数组中的第K个最大元素

Leetcode 215: 数组中的第K个最大元素 是一道非常经典的数组排序与查找问题，也是面试中非常常见的问题。考察重点包括：排序、堆排序、快速选择等多种方法，其中需要快速定位第K个最大元素。

---

问题描述 给定一个未排序的数组 nums，要求返回其中第 k 个最大的元素。注意，第 k 大的元素是按降序排列的第 k 个元素。

---

示例输入输出 输入: nums = [3,2,1,5,6,4], k = 2 输出: 5 输入: nums = [3,2,3,1,2,4,5,5,6], k = 4 输出: 4

---

解法 1：排序 思路 最简单直接的方法是对数组进行排序，然后返回第 k 大的元素。将数组按降序排序，第 k 大的元素就是索引为 k-1 的元素。

---

代码模板 import java.util.Arrays; class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); // 默认是升序排列 return nums[nums.length - k]; // 倒数第 k 个就是第 k 大 } }

---

复杂度分析 时间复杂度: O(n log n) 使用排序算法对数组排序，最小复杂度为 O(n log n)（如快速排序、归并排序）。 空间复杂度: O(1) （如果使用就地排序），或 O(n) （如果使用额外空间的排序算法）。

---

适用场景 当数据量较小（如 n < 1000）时可以快速实现，易于理解和写出。面试时作为最基础的解法，可以先写出来确保正确性。

---

解法 2：堆排序 (使用最小堆) 思路

最小堆可以维护一个包含 k 个元素的小顶堆，其中堆顶元素始终为当前堆中最小的元素。

遍历数组。对于当前元素： 如果堆大小小于 k，直接将元素加入堆。如果堆已经满，并且当前元素大于堆顶元素，则将堆顶元素替换为当前元素，并调整堆。

遍历完成后，堆顶元素就是第 k 大的元素。

---

代码模板 import java.util.PriorityQueue; class Solution { public int findKthLargest(int[] nums, int k) { // 初始化一个最小堆，容量为 k PriorityQueue<Integer> heap = new PriorityQueue<>(k); // 遍历数组 for (int num : nums) { if (heap.size() < k) { heap.offer(num); // 如果堆未满，直接加入 } else if (num > heap.peek()) { heap.poll(); // 弹出最小值 heap.offer(num); // 加入当前元素 } } // 返回堆顶元素 return heap.peek(); } }

---

复杂度分析 时间复杂度: O(n log k) 遍历数组需要 O(n)，每次堆的插入与删除操作需要 O(log k)。 空间复杂度: O(k) 堆中只存储 k 个元素。

---

适用场景 数据量较大，但 k 值较小，适合用堆来优化。中等规模数据场景的高效解决方案。

---

解法 3：快速选择 (Quickselect) 思路

快速选择是快速排序的变种，只关注目标元素所在的部分，不需要对整个数组完全排序。

随机选择一个枢轴 (pivot)；将数组分区，使 pivot 左侧的元素都小于 pivot，右侧的元素都大于 pivot；判断 pivot 的位置： 如果 pivot 恰好是第 n-k 大元素，则直接返回；如果 pivot 在第 n-k 的右侧，则在左半部分递归；如果 pivot 在第 n-k 的左侧，则在右半部分递归。

递归实现快速选择。

---

代码模板 import java.util.Random; class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; return quickSelect(nums, 0, n - 1, n - k); } private int quickSelect(int[] nums, int left, int right, int index) { // 分区操作 int pivot = partition(nums, left, right); if (pivot == index) { return nums[pivot]; // 找到结果 } else if (pivot < index) { return quickSelect(nums, pivot + 1, right, index); } else { return quickSelect(nums, left, pivot - 1, index); } } private int partition(int[] nums, int left, int right) { int pivot = nums[right]; // 选择最右侧元素为枢轴 int i = left - 1; // i 指向比 pivot 小的区域的最后一个元素 for (int j = left; j < right; j++) { if (nums[j] <= pivot) { // 把小于等于 pivot 的元素交换到左侧 i++; swap(nums, i, j); } } swap(nums, i + 1, right); return i + 1; // 返回 pivot 的最终位置 } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

---

复杂度分析 平均时间复杂度: O(n) 快速选择对每次迭代部分划分，平均情况下不断减少搜索范围。 最坏时间复杂度: O(n²) 在极端情况下（如总是选择不平衡的 pivot），时间复杂度退化为 O(n²)。 空间复杂度: O(1) 原地分区，不占用额外空间。

---

适用场景 当需要更高效的数据操作，而数据量较大时，非常适合快速选择。均值场景下效率优于排序和堆。

---

解法 4：使用内置库 思路 使用 Java 的内置库，如 Arrays.sort 或 PriorityQueue，快速获取目标元素。

---

代码模板 import java.util.Collections; import java.util.PriorityQueue; class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (int num : nums) { maxHeap.add(num); } for (int i = 1; i < k; i++) { maxHeap.poll(); } return maxHeap.poll(); } }

---

快速 AC 策略

首选快速选择 (Quickselect, 解法 3)：

平均时间复杂度 O(n)，适合处理大规模数据。适合面试或比赛中优先编写，凸显算法能力。

堆排序 (解法 2)：

O(n log k) 的效率，适合 k 较小的场景。实现简单，非常稳定。

排序 (解法 1)：

简单易实现，适合快速验证结果或小规模数据。

根据场景选择合适解法，可以快速 AC 本题！