我来给你讲解 LeetCode 第 215 题「数组中的第K个最大元素」。

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1：

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

示例 2：

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

解题思路循序渐进

方法一：直接排序（最直观）

def findKthLargest(nums, k):
    nums.sort()
    return nums[-k]

• 时间复杂度：O(n log n)，其中 n 是数组长度
• 空间复杂度：O(1)（如果使用原地排序）

优点：实现简单，代码清晰
缺点：当数组很大时，排序整个数组效率不高

方法二：堆排序（更高效）

我们可以使用最小堆来只维护前 k 个最大的元素：

import heapq

def findKthLargest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:  # 保持堆的大小为k
            heapq.heappop(heap)  # 弹出最小的元素
    return heap[0]  # 堆顶就是第k大的元素

工作原理：

1. 维护一个大小为 k 的最小堆
2. 遍历数组，将每个元素加入堆中
3. 当堆的大小超过 k 时，弹出最小的元素（堆顶）
4. 遍历完成后，堆顶就是第 k 大的元素

时间复杂度：O(n log k)，比完全排序更高效
空间复杂度：O(k)

方法三：快速选择算法（最优解）

基于快速排序的分区思想，但只处理包含目标的那一部分：

import random

def findKthLargest(nums, k):
    def quick_select(left, right, k_smallest):
        """返回第k小的元素（从0开始计数）"""
        if left == right:
            return nums[left]
        
        # 随机选择pivot
        pivot_index = random.randint(left, right)
        
        # 分区操作
        pivot_index = partition(left, right, pivot_index)
        
        if k_smallest == pivot_index:
            return nums[k_smallest]
        elif k_smallest < pivot_index:
            return quick_select(left, pivot_index - 1, k_smallest)
        else:
            return quick_select(pivot_index + 1, right, k_smallest)
    
    def partition(left, right, pivot_index):
        pivot_value = nums[pivot_index]
        # 将pivot移到末尾
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        
        store_index = left
        for i in range(left, right):
            if nums[i] < pivot_value:
                nums[store_index], nums[i] = nums[i], nums[store_index]
                store_index += 1
        
        # 将pivot移回正确位置
        nums[right], nums[store_index] = nums[store_index], nums[right]
        return store_index
    
    # 第k大的元素 = 第(n-k)小的元素
    return quick_select(0, len(nums) - 1, len(nums) - k)

算法步骤详解：

1. 转换目标：第k大的元素 = 第(n-k)小的元素（从0开始计数）

2. 分区过程：

   • 随机选择pivot（避免最坏情况）
   • 将数组分为三部分：小于pivot的、等于pivot的、大于pivot的
   • 返回pivot的最终位置

3. 递归选择：

   • 如果目标位置正好是pivot位置，直接返回
   • 如果目标位置在pivot左边，递归处理左半部分
   • 如果目标位置在pivot右边，递归处理右半部分

时间复杂度：平均O(n)，最坏O(n²)（但随机化后概率很低）
空间复杂度：O(1)（尾递归优化）

三种方法对比

关键要点

1. 理解"第k大"与"第k小"的转换：第k大 = 第(n-k+1)小
2. 快速选择算法的随机化很重要，避免最坏情况
3. 堆方法适合处理数据流，因为不需要一次性加载所有数据

这个算法在实际工程中很常用，比如找Top K元素、中位数等问题都可以用类似思路解决。