目录
- 215. 数组中的第 K 个最大元素 - 完整题解
- 1. 题目理解
- 2. 解题思路讨论
- 思路一：直接排序（基线方案）
- 思路二：最小堆（优先队列）
- 思路三：快速选择算法（Quick Select）
- 思路四：更适合 python3 的简单写法【⭐】
- 3. 代码实现（快速选择算法）
- 代码详细注释与逻辑解析
- 4. 替代解法：最小堆（Pythonic 写法）
- 5. 复杂度对比总结
- 6. 为什么快速选择是 O(n)？
- 7. 总结
215. 数组中的第 K 个最大元素 - 完整题解
1. 题目理解
题目描述：
给定一个未排序的整数数组 nums 和一个整数 k，你需要找到数组排序后第 k 个最大的元素。
- 注意：是排序后的第 k 个，而不是第 k 个不同的元素（即重复元素算多个）。
- 核心要求： 必须设计时间复杂度为 O(n) 的算法。
示例解析：
- 输入：
[3,2,1,5,6,4],k = 2- 排序后：
[1, 2, 3, 4, 5, 6] - 第 1 大是 6，第 2 大是 5。
- 输出：
5
- 排序后：
- 输入：
[3,2,3,1,2,4,5,5,6],k = 4- 排序后：
[1, 2, 2, 3, 3, 4, 5, 5, 6] - 从大到小数：6(1), 5(2), 5(3), 4(4)。
- 输出：
4
- 排序后：
难点分析：
最直观的方法是将数组排序，然后直接取第 k 个。但是，常规排序算法（如快速排序、归并排序）的时间复杂度是 \(O(n \log n)\)。题目明确要求 O(n)，这意味着我们不能对整个数组进行完全排序，只需要找到那个特定的元素即可。
2. 解题思路讨论
为了解决这个问题，我们通常有三种主要思路，我会由浅入深进行讲解。
思路一：直接排序（基线方案）
- 方法： 调用语言内置的排序函数，将数组从大到小排序，返回索引
k-1的元素。 - 复杂度： 时间 \(O(n \log n)\)，空间 \(O(1)\) 或 \(O(n)\)（取决于排序实现）。
- 评价： 代码最简单，但在本题中不符合时间复杂度要求。不过在面试中，如果面试官允许，可以作为保底方案提及。
思路二：最小堆（优先队列）
- 方法： 维护一个大小为
k的最小堆。遍历数组，如果堆未满则加入；如果堆满了且当前元素比堆顶（堆中最小值）大，则弹出堆顶，加入当前元素。遍历结束后，堆顶即为第 k 大元素。 - 复杂度： 时间 \(O(n \log k)\)，空间 \(O(k)\)。
- 评价： 当 \(k\) 远小于 \(n\) 时效率很高。但在最坏情况下（\(k \approx n\)），复杂度接近 \(O(n \log n)\)，严格来说不完全符合 O(n) 要求，但在工程实践中非常常用。
思路三：快速选择算法（Quick Select）
- 方法： 这是快速排序（Quick Sort）的变种。
- 选择一个“基准值”（pivot）。
- 将数组分为两部分：比基准值大的放左边，比基准值小的放右边（分区操作 partition）。
- 此时基准值所在的位置就是它排序后应该在的位置。
- 如果这个位置正好是第 k 大的位置，直接返回。
- 如果这个位置在目标左边，说明目标在右半部分，只递归右边。
- 如果这个位置在目标右边，说明目标在左半部分，只递归左边。
- 复杂度： 平均时间 \(O(n)\)，最坏时间 \(O(n^2)\)。
- 优化： 通过随机选择基准值，可以避免最坏情况，使算法在期望上稳定达到 \(O(n)\)。
- 评价： 这是本题的标准解法，完全符合题目对时间复杂度的要求。
思路四：更适合 python3 的简单写法【⭐】
发现前面的思路三超时了；
虽然思路三在算法层面上优雅，但是理解起来还是有些复杂；
下面这个我从 leetcode 题解里搬运的解法，更加清晰易懂，还不超时；
面试可以直接写这个。
直接放一版代码吧，很容易看懂：
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:# 随机选择基准数pivot = random.choice(nums)# 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中big, equal, small = [], [], []for num in nums:if num > pivot:big.append(num)elif num < pivot:small.append(num)else:equal.append(num)# 第 k 大元素在 big 中，递归划分if k <= len(big):return self.findKthLargest(big, k)# 第 k 大元素在 small 中，递归划分if len(nums) - len(small) < k:return self.findKthLargest(small, k - len(nums) + len(small))# 第 k 大元素在 equal 中，直接返回 pivotreturn pivot
3. 代码实现（快速选择算法）
下面提供基于 快速选择（Quick Select） 的 Python 3 代码。这是满足题目 \(O(n)\) 要求的标准解法。
import random
from typing import Listclass Solution:def findKthLargest(self, nums: List[int], k: int) -> int:"""主函数：寻找数组中第 k 个最大的元素"""# 目标：找到排序后索引为 target_index 的元素# 如果是升序排序，第 1 大在最后 (len-1)，第 k 大在 (len-k)target_index = len(nums) - k# 调用快速选择算法，在 nums 的 [0, len-1] 范围内查找return self.quickSelect(nums, 0, len(nums) - 1, target_index)def quickSelect(self, nums: List[int], left: int, right: int, target_index: int) -> int:"""快速选择核心逻辑:param nums: 数组:param left: 当前搜索范围的左边界:param right: 当前搜索范围的右边界:param target_index: 目标元素在升序排序后的索引:return: 目标元素的值"""# 1. 分区操作，返回基准值最终所在的索引pivot_index = self.partition(nums, left, right)# 2. 判断基准值位置与目标位置的关系if pivot_index == target_index:# 正好找到了return nums[pivot_index]elif pivot_index < target_index:# 基准值在目标左边，说明目标在右半部分 [pivot_index + 1, right]return self.quickSelect(nums, pivot_index + 1, right, target_index)else:# 基准值在目标右边，说明目标在左半部分 [left, pivot_index - 1]return self.quickSelect(nums, left, pivot_index - 1, target_index)def partition(self, nums: List[int], left: int, right: int) -> int:"""分区函数：将数组分为比基准值大和比基准值小的两部分这里我们采用“升序”逻辑的分区：左边小，右边大注意：因为我们要找第 k 大，对应升序数组的 len-k 位置，所以用升序分区是方便的"""# 【关键优化】随机选择基准值，防止在有序数组上退化为 O(n^2)# 随机选一个索引，将其交换到最右边作为 pivotrandom_index = random.randint(left, right)nums[random_index], nums[right] = nums[right], nums[random_index]pivot = nums[right] # 基准值i = left # i 指向“小于等于 pivot 区域”的下一个位置# 遍历数组，将小于等于 pivot 的数交换到左边for j in range(left, right):if nums[j] <= pivot:nums[i], nums[j] = nums[j], nums[i]i += 1# 最后将基准值放到中间正确的位置（i 的位置）# 此时：nums[left...i-1] <= pivot, nums[i] = pivot, nums[i+1...right] > pivotnums[i], nums[right] = nums[right], nums[i]return i # 返回基准值最终的索引
代码详细注释与逻辑解析
-
索引转换 (
target_index = len(nums) - k)：- 快速选择通常基于“升序”逻辑实现（左边小，右边大）。
- 第 1 大的元素在升序数组的最后，索引是
len - 1。 - 第 k 大的元素在升序数组的索引是
len - k。 - 例如：
[1, 2, 3, 4, 5], k=1 (最大是 5), index = 5-1 = 4。k=2 (最大是 4), index = 5-2 = 3。
-
随机化 (
random.randint)：- 这是保证 \(O(n)\) 的关键。如果不随机，当数组本身有序时，每次分区都极不平衡（一边 0 个，一边 n-1 个），会导致递归深度为 \(n\)，总复杂度变为 \(O(n^2)\)。
- 随机化后，期望的递归深度是 \(\log n\)，每层处理 \(n\) 个元素，总期望复杂度为 \(O(n)\)。
-
分区 (
partition)：- 这是快速排序的核心。我们选定一个
pivot。 - 变量
i维护的是“小于等于 pivot 区域”的边界。 - 变量
j负责遍历。 - 如果
nums[j] <= pivot，说明它属于左边，把它交换到i的位置，然后i右移。 - 最后把
pivot从末尾交换到i的位置，此时pivot左边的都比它小，右边的都比它大。
- 这是快速排序的核心。我们选定一个
4. 替代解法：最小堆（Pythonic 写法）
虽然题目要求 \(O(n)\)，但在实际 Python 开发或某些面试场景（如果不强制卡 \(O(n)\)）中，使用堆是非常简洁且高效的写法。
import heapq
from typing import Listclass SolutionHeap:def findKthLargest(self, nums: List[int], k: int) -> int:"""使用最小堆维护前 k 个最大的元素时间复杂度：O(n log k)空间复杂度：O(k)"""# Python 的 heapq 是最小堆# 我们维护一个大小为 k 的最小堆# 堆顶永远是这 k 个元素中最小的，也就是第 k 大的候选者heap = []for num in nums:if len(heap) < k:# 堆还没满，直接加入heapq.heappush(heap, num)else:# 堆满了，如果当前数字比堆顶大，说明堆顶不可能是第 k 大了# 弹出堆顶，加入当前数字if num > heap[0]:heapq.heapreplace(heap, num)# 遍历结束后，堆顶即为第 k 大的元素return heap[0]# 或者使用 Python 内置的 nlargest 函数，底层也是堆优化def findKthLargestBuiltIn(self, nums: List[int], k: int) -> int:return heapq.nlargest(k, nums)[-1]
5. 复杂度对比总结
| 解法 | 时间复杂度 (平均) | 时间复杂度 (最坏) | 空间复杂度 | 是否满足题目 O(n) | 备注 |
|---|---|---|---|---|---|
| 直接排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(1)\) | ❌ 否 | 最简单，但不符合题目硬性要求 |
| 最小堆 | \(O(n \log k)\) | \(O(n \log k)\) | \(O(k)\) | ❌ 否 (除非 k 是常数) | 适合 \(k \ll n\) 的场景，代码简洁 |
| 快速选择 | \(O(n)\) | \(O(n^2)\) | \(O(\log n)\) (递归栈) | ✅ 是 | 本题标准解法，需随机化优化 |
| BFPRT 算法 | \(O(n)\) | \(O(n)\) | \(O(\log n)\) | ✅ 是 | 确定性 O(n)，但实现过于复杂，面试极少考 |
注：快速选择的空间复杂度主要来自递归调用栈，平均深度为 \(\log n\)。
6. 为什么快速选择是 O(n)？
这是一个常见的面试追问点。
快速选择每次递归只处理一半的数据（期望情况下）。
- 第一轮处理 \(n\) 个元素。
- 第二轮期望处理 \(n/2\) 个元素。
- 第三轮期望处理 \(n/4\) 个元素。
- ...
- 总工作量 = $n + n/2 + n/4 + n/8 + ... = n \times (1 + 1/2 + 1/4 + ...) $
- 括号内是一个等比数列，和收敛于 2。
- 所以总时间复杂度 \(\approx 2n\)，即 \(O(n)\)。
7. 总结
- 审题关键：看到“第 K 大/小”且要求 \(O(n)\)，第一时间应想到 快速选择 (Quick Select) 算法。
- 实现细节：务必加入随机化选择 pivot，否则在 LeetCode 的测试用例（包含大量有序数组）下会超时。
- 索引转换：注意第 k 大对应升序数组的
len - k索引，不要搞反。 - 备选方案：如果面试中允许 \(O(n \log k)\)，使用最小堆代码更短，不易出错。
希望这份题解能帮助你彻底理解这道经典题目！