LeetCode 215题"数组中的第K个最大元素"要求我们在一个未排序的整数数组中找到第K个最大的元素。需要注意的是，这里要求的是数组排序后的第K个最大元素，而不是第K个不同的元素。题目还特别要求我们设计并实现时间复杂度为O(n)的算法来解决此问题。
示例1：
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例2：
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
解题思路
方法一：堆排序
堆排序是解决这个问题的常用方法之一。我们可以使用大顶堆来实现，具体步骤如下：
构建一个大顶堆
依次将堆顶元素（当前最大值）与堆的最后一个元素交换
调整堆结构，使其满足大顶堆的性质
重复步骤2和3，共执行k次
第k次交换后的堆顶元素即为第k个最大元素
堆排序的关键在于大顶堆的构建和调整过程。下面我们来详细了解大顶堆的构建过程：
方法二：快速选择算法
快速选择算法是基于快速排序的一种改进算法，它可以在平均O(n)的时间复杂度内找到数组中第k个最大元素。其基本思想是：
选择一个基准元素
将数组分区，使得小于基准的元素在左边，大于基准的元素在右边
判断基准元素的位置与k的关系：
如果基准元素的位置等于k-1，则基准元素就是第k个最大元素
如果基准元素的位置大于k-1，则在左半部分继续查找
如果基准元素的位置小于k-1，则在右半部分继续查找
算法复杂度分析
时间复杂度
堆排序：O(n + klogn)，其中n为数组长度，k为要求的第k大元素的k值。初始化建堆的时间复杂度为O(n)，每次调整堆的时间复杂度为O(logn)，共需要k次调整。
快速选择算法：平均时间复杂度为O(n)，最坏情况下为O(n^2)。但通过随机选择基准元素，可以将最坏情况的概率降到极低。
空间复杂度
堆排序：O(1)，可以原地排序，不需要额外空间
快速选择算法：O(logn)，递归调用栈所需的空间，最坏情况下为O(n)
关键难点分析
堆排序的难点
堆的构建：需要从最后一个非叶子节点开始，自底向上调整堆结构
堆的调整：在每次交换堆顶元素后，需要重新调整堆结构以维持大顶堆的性质
边界条件处理：需要注意数组索引的边界条件，避免数组越界
快速选择算法的难点
基准元素的选择：基准元素的选择会影响算法效率，最坏情况下时间复杂度可能达到O(n^2)
分区操作：如何高效地将数组分区是实现快速选择算法的关键
递归终止条件：需要正确设置递归终止条件，避免无限递归
五种语言实现
Java实现（最小堆法）
class Solution {public int findKthLargest(int[] nums, int k) {// 使用最小堆实现：维护一个大小为k的最小堆// 堆顶元素即为当前第k大元素，这种实现更节省内存空间PriorityQueue<Integer> minHeap = new PriorityQueue<>();// 遍历数组元素for (int num : nums) {// 将当前元素加入堆minHeap.add(num);// 当堆大小超过k时，移除堆顶元素（当前最小的元素）// 这样可以确保堆中始终是当前最大的k个元素if (minHeap.size() > k) {minHeap.poll();}}// 堆顶元素即为第k个最大元素return minHeap.peek();}}
Python实现（堆排序）
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:"""使用堆排序算法找到数组中第k个最大元素"""def max_heapify(arr, i, end):"""大顶堆调整函数：确保以i为根的子树满足大顶堆性质arr: 待调整的数组i: 当前需要调整的节点索引end: 堆的最后一个元素索引"""j = 2 * i + 1 # j为i的左子节点索引while j <= end: # 当子节点存在时继续调整# 比较左右子节点，取较大者的索引if j + 1 <= end and arr[j + 1] > arr[j]:j += 1 # 右子节点较大，将j指向右子节点# 如果当前节点小于其子节点中的较大者，交换它们if arr[i] < arr[j]:arr[i], arr[j] = arr[j], arr[i]i = j # 继续调整交换后的子节点j = 2 * i + 1 # 更新左子节点索引else:break # 当前节点已满足大顶堆性质，结束调整n = len(nums)# 建堆（大顶堆）：从最后一个非叶子节点开始自底向上调整# 最后一个非叶子节点索引为n//2 - 1for i in range(n // 2 - 1, -1, -1):max_heapify(nums, i, n - 1)# 排序过程：依次将堆顶元素（当前最大值）放置到数组尾部# 共执行k次，即可找到第k个最大元素for j in range(n - 1, n - k - 1, -1):# 将堆顶元素（当前最大值）与当前尾部元素交换nums[0], nums[j] = nums[j], nums[0]# 调整堆：排除已排好序的尾部元素，从堆顶开始调整max_heapify(nums, 0, j - 1)# 返回第k个最大元素（数组中倒数第k个元素）return nums[-k]
Go实现（快速选择算法）
// findKthLargest 查找数组中第k个最大元素func findKthLargest(nums []int, k int) int {// 使用快速选择算法，初始查找范围为整个数组return quickSelect(nums, 0, len(nums)-1, k)}// quickSelect 快速选择算法实现// nums: 待查找的数组// left: 当前查找范围的左边界// right: 当前查找范围的右边界// k: 要查找的第k个最大元素func quickSelect(nums []int, left, right, k int) int {// 对数组进行分区，返回基准元素的最终位置pivot := partition(nums, left, right)// 判断基准元素是否为第k个最大元素// 第k个最大元素在排序后数组中的索引为len(nums)-kif pivot == len(nums)-k {return nums[pivot] // 找到目标元素，返回其值} else if pivot < len(nums)-k {// 目标元素在右半部分，递归查找右半部分return quickSelect(nums, pivot+1, right, k)} else {// 目标元素在左半部分，递归查找左半部分return quickSelect(nums, left, pivot-1, k)}}// partition 分区函数：选择最右侧元素作为基准，将数组分为两部分// 返回基准元素的最终位置索引func partition(nums []int, left, right int) int {pivot := nums[right] // 选择最右侧元素作为基准i := left // i指向小于基准区域的右边界// 遍历数组，将小于基准的元素交换到左侧区域for j := left; j < right; j++ {if nums[j] < pivot {// 当前元素小于基准，交换到左侧区域nums[i], nums[j] = nums[j], nums[i]i++ // 扩展小于基准的区域}}// 将基准元素放到其最终位置（小于基准区域和大于基准区域的中间）nums[i], nums[right] = nums[right], nums[i]return i // 返回基准元素的索引}
Rust实现（最大堆法）
// 导入标准库中的二叉堆（最大堆）use std::collections::BinaryHeap;impl Solution {// 查找数组中第k个最大元素pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {// 将k转换为usize类型，用于数组索引let k = k as usize;// 创建一个最大堆let mut heap = BinaryHeap::new();// 将所有元素推入堆中，堆会自动维护最大堆性质for num in nums {heap.push(num);}// 弹出堆顶元素k-1次，此时堆顶元素即为第k个最大元素for _ in 0..k-1 {heap.pop();}// 弹出并返回第k个最大元素heap.pop().unwrap()}}
C++实现（快速选择算法）
class Solution {public:// 查找数组中第k个最大元素int findKthLargest(vector<int>& nums, int k) {// 使用快速选择算法，初始查找范围为整个数组return quickSelect(nums, 0, nums.size() - 1, k);}private:// 快速选择算法实现// nums: 待查找的数组// left: 当前查找范围的左边界// right: 当前查找范围的右边界// k: 要查找的第k个最大元素int quickSelect(vector<int>& nums, int left, int right, int k) {// 对数组进行分区，返回基准元素的最终位置int pivot = partition(nums, left, right);// 判断基准元素是否为第k个最大元素// 第k个最大元素在排序后数组中的索引为nums.size()-kif (pivot == nums.size() - k) {return nums[pivot]; // 找到目标元素，返回其值} else if (pivot < nums.size() - k) {// 目标元素在右半部分，递归查找右半部分return quickSelect(nums, pivot + 1, right, k);} else {// 目标元素在左半部分，递归查找左半部分return quickSelect(nums, left, pivot - 1, k);}}// 分区函数：选择最右侧元素作为基准，将数组分为两部分// 返回基准元素的最终位置索引int partition(vector<int>& nums, int left, int right) {int pivot = nums[right]; // 选择最右侧元素作为基准int i = left; // i指向小于基准区域的右边界// 遍历数组，将小于基准的元素交换到左侧区域for (int j = left; j < right; j++) {if (nums[j] < pivot) {// 当前元素小于基准，交换到左侧区域swap(nums[i], nums[j]);i++; // 扩展小于基准的区域}}// 将基准元素放到其最终位置（小于基准区域和大于基准区域的中间）swap(nums[i], nums[right]);return i; // 返回基准元素的索引}};
总结
本文详细解析了LeetCode 215题"数组中的第K个最大元素"，介绍了两种主要解题方法：堆排序和快速选择算法。堆排序的时间复杂度为O(n + klogn)，空间复杂度为O(1)；快速选择算法的平均时间复杂度为O(n)，但最坏情况下可能达到O(n^2)，空间复杂度为O(logn)。
在实际应用中，我们需要根据具体问题选择合适的算法。如果对时间复杂度要求较高且数据量较大，建议使用快速选择算法；如果对最坏情况的稳定性要求较高，建议使用堆排序。
通过这道题，我们不仅学习了解决"第K个最大元素"问题的具体方法，更重要的是掌握了堆和快速选择这两种重要的数据结构和算法思想，这些思想在解决其他类似问题时也会非常有用。