【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(Nlog⁡N)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 大元素的索引刚好在左半区那我们完全不需要去管右半区直接递归左半区即可因为每次都能砍掉大约一半的数据量NN/2N/4...N N/2 N/4 ...NN/2N/4...它的时间复杂度收敛成了极其优雅的O(N)O(N)O(N) C 代码实现 (Hoare 划分模板)classSolution{public:intfindKthLargest(vectorintnums,intk){// 调用 quickSelect注意题目要求的 k 是第 k 大对应降序数组的索引是 k - 1returnquickSelect(nums,0,nums.size()-1,k);}private:intquickSelect(vectorintnums,intl,intr,intk){if(lr)returnnums[l];// 递归终止条件// 1. 选取基准值 pivot取中间元素可避免在有序数组下退化intpivotnums[l(r-l)/2];intil-1,jr1;// 2. 降序划分过程 (Hoare Partition)while(ij){doi;while(nums[i]pivot);doj--;while(nums[j]pivot);if(ij)swap(nums[i],nums[j]);}// 3. 核心剪枝判断第 k 大的元素落在哪个区间只去那一个区间寻找if(k-1j)returnquickSelect(nums,l,j,k);returnquickSelect(nums,j1,r,k);}}; 解法二优先队列 / 小顶堆 (海量数据流最优解)如果在面试中面试官加上一个条件“如果是海量数据如 100 亿条日志内存放不下整个数组怎么办” 这时候 QuickSelect 就失效了必须请出优先队列小顶堆。核心思想我们要维护一个大小始终为KKK的小顶堆。遍历数据流遇到新元素直接入堆。如果堆的容量超过了KKK就把堆里最小的元素堆顶踢出去。大浪淘沙之后等所有数据遍历完这个大小为KKK的堆里留下的就是全场最大的KKK个数而此时的堆顶刚好就是这 K 个数里最小的也就是我们要找的第 K 大的数 C 代码实现 (大小为 K 的小顶堆)classSolution{public:intfindKthLargest(vectorintnums,intk){// C 默认是大顶堆通过 greaterint 定义为小顶堆priority_queueint,vectorint,greaterintminHeap;for(inti0;inums.size();i){minHeap.push(nums[i]);// 无脑入堆// 只要堆的大小超过了 K就把最小的那个堆顶踢出去if(minHeap.size()k){minHeap.pop();}}// 最终堆顶留下的就是第 K 大的元素returnminHeap.top();}};