【Hot 100 刷题计划】 LeetCode 215. 数组中的第K个最大元素 | C++ 快速选择与堆排序题解
LeetCode 215. 数组中的第K个最大元素 | C++ 快速选择与小顶堆双解法
📌 题目描述
题目级别：中等
给定整数数组nums和整数k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
你必须设计并实现时间复杂度为O(N)O(N)O(N)的算法解决此问题。
- 示例 1:
输入:[3,2,1,5,6,4],k = 2
输出:5
💡 破题思路：Top K 问题的绝代双骄
面对 Top K 问题，直接调用sort()排序（O(NlogN)O(N \log N)O(NlogN)）显然不是面试官想要的。在大厂面试中，这道题的标准答案分为两个方向：追求数学极限的O(N)O(N)O(N)解法，以及应对海量工程数据的解法。
🚀 解法一：快速选择算法 QuickSelect (严格 O(N) 面试满分解)
题目加粗强调了时间复杂度必须是O(N)O(N)O(N)，破局的唯一解法就是快速选择算法（QuickSelect）。
它的核心思想脱胎于经典的“快速排序（Quick Sort）”：
- 区域划分（Partition）：随便挑一个基准值（Pivot），把比它大的数扔到左边，比它小的数扔到右边（降序划分）。
- 精准剪枝（灵魂所在）：一次划分后，基准值就落在了最终正确的排名位置。如果我们要找的第 K 大元素的索引刚好在左半区，那我们完全不需要去管右半区，直接递归左半区即可！
因为每次都能砍掉大约一半的数据量（N+N/2+N/4+...N + N/2 + N/4 + ...N+N/2+N/4+...），它的时间复杂度收敛成了极其优雅的O(N)O(N)O(N)！
💻 C++ 代码实现 (Hoare 划分模板)
classSolution{public:intfindKthLargest(vector<int>&nums,intk){// 调用 quickSelect，注意题目要求的 k 是第 k 大，对应降序数组的索引是 k - 1returnquickSelect(nums,0,nums.size()-1,k);}private:intquickSelect(vector<int>&nums,intl,intr,intk){if(l==r)returnnums[l];// 递归终止条件// 1. 选取基准值 pivot，取中间元素可避免在有序数组下退化intpivot=nums[l+(r-l)/2];inti=l-1,j=r+1;// 2. 降序划分过程 (Hoare Partition)while(i<j){doi++;while(nums[i]>pivot);doj--;while(nums[j]<pivot);if(i<j)swap(nums[i],nums[j]);}// 3. 核心剪枝：判断第 k 大的元素落在哪个区间，只去那一个区间寻找if(k-1<=j)returnquickSelect(nums,l,j,k);returnquickSelect(nums,j+1,r,k);}};🏆 解法二：优先队列 / 小顶堆 (海量数据流最优解)
如果在面试中，面试官加上一个条件：“如果是海量数据（如 100 亿条日志），内存放不下整个数组怎么办？” 这时候 QuickSelect 就失效了，必须请出优先队列（小顶堆）。
核心思想：
我们要维护一个大小始终为KKK的小顶堆。
遍历数据流，遇到新元素直接入堆。如果堆的容量超过了KKK，就把堆里最小的元素（堆顶）踢出去。
大浪淘沙之后，等所有数据遍历完，这个大小为KKK的堆里留下的就是全场最大的KKK个数，而此时的堆顶，刚好就是这 K 个数里最小的，也就是我们要找的第 K 大的数！
💻 C++ 代码实现 (大小为 K 的小顶堆)
classSolution{public:intfindKthLargest(vector<int>&nums,intk){// C++ 默认是大顶堆，通过 greater<int> 定义为小顶堆priority_queue<int,vector<int>,greater<int>>minHeap;for(inti=0;i<nums.size();i++){minHeap.push(nums[i]);// 无脑入堆// 只要堆的大小超过了 K，就把最小的那个（堆顶）踢出去if(minHeap.size()>k){minHeap.pop();}}// 最终堆顶留下的，就是第 K 大的元素returnminHeap.top();}};