文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析思路1快速选择思路2小顶堆2、解题代码思路1快速选择思路2小顶堆三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接215.数组中的第K个最大元素2、题目描述二、个人思路整理1、思路分析思路1快速选择基于快速排序的partition思想。找“第k kk个最大元素”等价于找升序排序后索引为target nums.size() - k的元素。核心逻辑每次随机选取一个基准值pivot进行划分使得 pivot 左边的元素都小于它右边的元素都大于它pivot 最终落位在下标p pp。若p t a r g e t p targetptarget直接返回 nums[p]。若p t a r g e t p targetptarget说明目标在右半部分只需递归/迭代处理右半区间。若p t a r g e t p targetptarget说明目标在左半部分只需递归/迭代处理左半区间。关键点必须引入随机化选取 pivot否则在面对极端用例如全降序、全重复元素时每次切分极度不均衡时间复杂度会退化为O ( n 2 ) O(n^2)O(n2)导致超时。思路2小顶堆维护一个容量为k kk的小顶堆核心逻辑遍历数组将元素推入小顶堆。当堆的大小超过k kk时弹出堆顶当前最小的元素。遍历结束后堆中保留的就是数组中最大的k kk个数而堆顶恰好是这k kk个数中最小的一个即第k kk大元素。2、解题代码思路1快速选择classSolution{public:intfindKthLargest(vectorintnums,intk){// 第 k 个最大元素对应升序排序后的下标 (nums.size() - k)inttargetnums.size()-k;intleft0,rightnums.size()-1;while(leftright){// 随机选取 pivot 避免全升序/全降序等极端测试用例退化为O(n^2)intpivotIndexleftrand()%(right-left1);intppartition(nums,left,right,pivotIndex);if(ptarget){returnnums[p];// 命中目标位置直接返回}elseif(ptarget){leftp1;// 目标在右半部分收缩左边界}else{rightp-1;// 目标在左半部分收缩右边界}}return-1;}private:intpartition(vectorintnums,intleft,intright,intpivotIndex){intpivotValnums[pivotIndex];// 将基准值暂存到最右端swap(nums[pivotIndex],nums[right]);intstoreIndexleft;// 将小于 pivotVal 的元素逐一移动到左侧for(intileft;iright;i){if(nums[i]pivotVal){swap(nums[i],nums[storeIndex]);storeIndex;}}// 将基准值放回正确的分界位置swap(nums[storeIndex],nums[right]);returnstoreIndex;}};复杂度分析时间复杂度O ( n ) O(n)O(n)。每次只对单侧递归期望遍历n n / 2 n / 4 ⋯ 2 n n n/2 n/4 \dots 2nnn/2n/4⋯2n个元素最坏为O ( n 2 ) O(n^2)O(n2)。空间复杂度O ( 1 ) O(1)O(1)。迭代原地交换。思路2小顶堆classSolution{public:intfindKthLargest(vectorintnums,intk){// 维护一个元素递增的小顶堆堆顶始终为堆内最小值priority_queueint,vectorint,greaterintminHeap;for(intnum:nums){minHeap.push(num);// 堆容量超过 k 时弹出最小值始终保持堆中存放的是遍历过的前 k 个最大值if(minHeap.size()k){minHeap.pop();}}// 遍历结束后前 k 个最大元素中最小的那个堆顶即为第 k 大元素returnminHeap.top();}};复杂度分析时间复杂度O ( n log ⁡ k ) O(n \log k)O(nlogk)。遍历n nn个元素且每个元素进出容量为k kk的堆。空间复杂度O ( k ) O(k)O(k)。堆中最多保存k kk个元素。三、知识风暴快速选择Quickselect是本题的核心算法思想。它基于快速排序的partition划分通过「只处理目标所在的那一侧」来大幅降低复杂度是解决「第 K 大/小元素」类问题的经典高效做法。理解划分过程与随机化 pivot 的必要性对掌握本题至关重要。算法核心思想单侧递归每次partition后基准值会落在最终排序位置p pp。若p pp恰好是目标下标target直接返回否则只需递归处理目标所在的那一侧另一侧直接丢弃从而将期望复杂度降到O ( n ) O(n)O(n)。随机化 pivot必须随机选取基准值否则面对全升序、全降序或大量重复元素时每次划分极度不均衡复杂度会退化为O ( n 2 ) O(n^2)O(n2)导致超时。与快速排序的区别快速排序需要对划分后的左右两侧都递归排序而快速选择只对包含目标的那一侧继续处理因此平均更快。常见对比快速选择 vs 小顶堆快速选择期望时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)原地交换。适合一次性求第 K 大且不要求保持前 K 个元素的顺序。小顶堆时间复杂度O ( n log ⁡ k ) O(n \log k)O(nlogk)空间复杂度O ( k ) O(k)O(k)。适合数据量极大、无法一次性载入内存的流式场景或需要多次查询前 K 大元素时。共同点两者都能在不必完整排序的前提下找到第 K 大元素。区别在于快速选择会修改原数组顺序而小顶堆不修改原数组。“快速选择”设计思想核心思想利用partition的「基准值落位」特性将问题规模每次缩小一半左右。新基准值落位后比较p pp与target的大小关系即可确定目标在左半还是右半从而只处理一侧。与本题的联系第 K 个最大元素等价于升序排序后下标为nums.size() - k的元素。通过快速选择我们无需完整排序就能定位到该下标对应的元素。注意事项partition返回的是基准值在当前区间内的相对位置需要结合区间左边界换算成全局下标再与target比较。使用要点循环代替递归用while (left right)迭代收缩区间避免递归带来的栈开销也便于控制边界。随机化选取pivotIndex left rand() % (right - left 1)再与right交换保证每次划分的随机性。边界收缩p target时令left p 1p target时令right p - 1p target时直接返回。结果返回循环结束时若未命中理论上不会发生返回-1作为兜底。算法变体与扩展数组中的第K个最大元素LeetCode 215本题快速选择的标准应用。数组中的第K个最小元素将target改为k - 1即可思路完全一致。最小的K个数剑指 Offer 40快速选择定位后左侧区间即为最小的 K 个数是本题的变体。数据流中的第 K 大元素LeetCode 703动态数据流场景改用小顶堆维护前 K 大是堆解法的进阶应用。相关 LeetCode 例题215. 数组中的第K个最大元素快速选择 小顶堆703. 数据流中的第K大元素小顶堆 动态数据流剑指 Offer 40. 最小的k个数快速选择 区间划分973. 最接近原点的 K 个点快速选择 自定义比较