我来给你讲解 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

解题思路

方法一：排序（最直接）

最简单的思路是对数组进行排序，然后取第 k 个最大的元素。

def findKthLargest(nums, k):
    nums.sort()
    return nums[-k]  # 排序后第k大就是倒数第k个元素

时间复杂度： O(n log n)
空间复杂度： O(1)

这种方法简单但不够高效，我们需要寻找更优的解法。

方法二：堆（优先队列）

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

1. 创建一个小顶堆（最小堆）
2. 遍历数组，将元素加入堆中
3. 如果堆的大小超过k，就弹出最小的元素
4. 最后堆顶就是第k大的元素

import heapq

def findKthLargest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # 弹出最小的元素
    return heap[0]

时间复杂度： O(n log k)
空间复杂度： O(k)

这种方法比排序更高效，特别是当k远小于n时。

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

这是快速排序的变种，基于分治思想：

算法步骤：

1. 选择基准值（pivot）：从数组中随机选择一个元素作为基准
2. 分区（partition）：将数组重新排列，使得比基准大的元素都在左边，比基准小的元素都在右边
3. 判断位置：
   • 如果基准的索引正好是k-1，那么基准就是第k大的元素
   • 如果基准的索引大于k-1，说明第k大的元素在左半部分
   • 如果基准的索引小于k-1，说明第k大的元素在右半部分

import random

def findKthLargest(nums, k):
    def partition(left, right, pivot_index):
        pivot_value = nums[pivot_index]
        # 将基准值移到末尾
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        
        store_index = left
        for i in range(left, right):
            if nums[i] > pivot_value:  # 注意：我们要找第k大，所以用大于号
                nums[store_index], nums[i] = nums[i], nums[store_index]
                store_index += 1
        
        # 将基准值移到正确位置
        nums[right], nums[store_index] = nums[store_index], nums[right]
        return store_index
    
    def select(left, right, k_smallest):
        if left == right:
            return nums[left]
        
        # 随机选择基准值
        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 select(left, pivot_index - 1, k_smallest)
        else:
            return select(pivot_index + 1, right, k_smallest)
    
    # 第k大元素就是排序后第(n-k)小的元素
    return select(0, len(nums) - 1, len(nums) - k)

时间复杂度： 平均O(n)，最坏O(n²)（但随机化后概率很低）
空间复杂度： O(1)（原地修改）

关键点总结

1. 排序法最简单但效率不高
2. 堆方法适合k远小于n的情况
3. 快速选择是理论上的最优解，平均时间复杂度为O(n)
4. 快速选择算法的核心是分区操作和递归选择

实际应用

这个算法在现实中有很多应用，比如：

• 找考试成绩的前k名
• 推荐系统中的Top-K推荐
• 数据分析中的百分位数计算

理解这个题目有助于掌握分治思想和快速排序的变种应用。