【力扣100题】91.数组中的第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

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

二、解题思路总览

三、方法一：快速选择（推荐）

3.1 核心思想

快速选择是基于快速排序的选择算法，每次 partition 后只递归一边，所以时间复杂度是 O(n)。

3.2 算法流程图

原始数组: [3, 2, 1, 5, 6, 4], k = 2 目标: 找第 2 大的元素，即 target_index = 6 - 2 = 4 初始状态: +---+---+---+---+---+---+ | 3 | 2 | 1 | 5 | 6 | 4 | +---+---+---+---+---+---+ L R +------------------------------------------------------------+ | Step 1: partition(0, 5) | | | | 随机选择 pivot = nums[3] = 5 | | 交换到 left: [5, 2, 1, 3, 6, 4] | | | | 双指针扫描: | | i -> <- j | | [5, 2, 1, 3, 6, 4] | | | | 交换 2 和 6: [5, 2, 1, 3, 6, 4] -> i++,j-- -> i=3,j=2 | | i >= j，退出循环 | | 交换 nums[left] 和 nums[j]: [3, 2, 1, 5, 6, 4] | | 返回 pivot_index = 3 | +------------------------------------------------------------+ 比较: pivot_index(3) vs target_index(4) pivot_index < target_index -> 搜索右半部分 [4, 5] +------------------------------------------------------------+ | Step 2: partition(4, 5) | | | | 随机选择 pivot = nums[5] = 4 | | 交换到 left: [3, 2, 1, 5, 4, 6] | | | | 双指针扫描: | | i -> <- j | | [3, 2, 1, 5, 4, 6] | | | | i >= j，退出循环 | | 交换 nums[left] 和 nums[j]: [3, 2, 1, 5, 4, 6] | | 返回 pivot_index = 4 | +------------------------------------------------------------+ 比较: pivot_index(4) == target_index(4) -> 找到答案! 结果: nums[4] = 4

3.3 完整代码

classSolution{public:intpartition(vector<int>&nums,intleft,intright){// 随机选择 pivot，避免最坏情况inti=left+rand()%(right-left+1);intpivot=nums[i];swap(nums[i],nums[left]);i=left+1;intj=right;while(1){while(i<=j&&nums[i]<pivot){i++;}while(i<=j&&nums[j]>pivot){j--;}if(i>=j)break;swap(nums[i],nums[j]);i++;j--;}swap(nums[left],nums[j]);returnj;}intfindKthLargest(vector<int>&nums,intk){srand(time(NULL));intn=nums.size();inttarget_index=n-k;intleft=0,right=n-1;while(true){inti=partition(nums,left,right);if(i==target_index){returnnums[i];}if(i>target_index){right=i-1;}else{left=i+1;}}}};

3.4 复杂度分析

空间复杂度：O(1)

时间复杂度推导：

T(n) = n + n/2 + n/4 + n/8 + ... = n * (1 + 1/2 + 1/4 + ...) = n * 2 = O(n)

四、方法二：小顶堆（适合大数据流）

4.1 核心思想

维护一个大小为 k 的小顶堆，堆顶是当前第 k 大的元素。遍历数组时，比堆顶大的元素才入堆，最终堆顶就是答案。

4.2 算法流程图

数组: [3, 2, 1, 5, 6, 4], k = 2 +------------------------------------------------------------+ | 初始化小顶堆（大小限制为 k=2） | +------------------------------------------------------------+ 遍历元素: +------------------------------------------------------------+ | 插入 3: 堆=[3] | | 3 | | | | 插入 2: 堆=[2,3] | | 2 | | / | | 3 | +------------------------------------------------------------+ +------------------------------------------------------------+ | 插入 1: 堆=[1,3,2] -> 调整 -> 堆=[1,3,2]（大小超过2，删除最小）| | 1 | | / \ | | 3 2 | | | | 删除堆顶 1: 堆=[2,3] | | 2 | | / | | 3 | +------------------------------------------------------------+ +------------------------------------------------------------+ | 插入 5: 5 > 堆顶(2)，入堆 | | 堆=[2,3,5] -> 调整 -> 堆=[2,5,3]（大小超过2，删除最小） | | 2 | | / \ | | 3 5 | | | | 删除堆顶 2: 堆=[3,5] | | 3 | | / | | 5 | +------------------------------------------------------------+ +------------------------------------------------------------+ | 插入 6: 6 > 堆顶(3)，入堆 | | 堆=[3,5,6] -> 调整 -> 堆=[3,5,6]（大小超过2，删除最小） | | 3 | | / \ | | 5 6 | | | | 删除堆顶 3: 堆=[5,6] | | 5 | | / | | 6 | +------------------------------------------------------------+ +------------------------------------------------------------+ | 插入 4: 4 > 堆顶(5)，入堆 | | 堆=[4,6,5] -> 调整 -> 堆=[4,5,6]（大小超过2，删除最小） | | 4 | | / \ | | 5 6 | | | | 删除堆顶 4: 堆=[5,6] | +------------------------------------------------------------+ 最终堆顶 = 5，即第 2 大的元素

4.3 完整代码

classSolution{public:intfindKthLargest(vector<int>&nums,intk){priority_queue<int,vector<int>,greater<int>>minHeap;for(intnum:nums){minHeap.push(num);if(minHeap.size()>k){minHeap.pop();}}returnminHeap.top();}};

4.4 复杂度分析

五、方法三：大顶堆 + 弹出

5.1 核心思想

将整个数组建成大顶堆，然后弹出 k 次堆顶，最后一次弹出的就是第 k 大的元素。

5.2 算法流程图

数组: [3, 2, 1, 5, 6, 4], k = 2 +------------------------------------------------------------+ | Step 1: 建大顶堆（从最后一个非叶子节点开始下沉） | +------------------------------------------------------------+ 初始数组完全二叉树: 3 / \ 2 1 / \ / 5 6 4 下沉 i=2 (节点2): 3 / \ 6 1 / \ / 5 2 4 下沉 i=1 (节点3): 6 / \ 5 4 / \ / 3 2 1 下沉 i=0 (节点6): 6 / \ 5 4 / \ / 3 2 1 +------------------------------------------------------------+ | Step 2: 弹出堆顶 k=2 次 | +------------------------------------------------------------+ 第1次弹出: 堆顶 6 与 末尾 1 交换 -> [1,5,4,3,2,6] 堆大小-1，堆顶下沉 -> [5,3,4,1,2,6] 堆=[5,3,4,1,2] 第2次弹出: 堆顶 5 与 末尾 2 交换 -> [2,3,4,1,5,6] 堆大小-1，堆顶下沉 -> [4,3,2,1,5,6] 堆=[4,3,2,1] 答案 = 4（弹出的第2个元素）

5.3 完整代码

classSolution{public:intfindKthLargest(vector<int>&nums,intk){intn=nums.size();// 建大顶堆for(inti=n/2-1;i>=0;i--){heapify(nums,n,i);}// 弹出 k 次for(inti=0;i<k;i++){swap(nums[0],nums[n-1-i]);heapify(nums,n-1-i,0);}returnnums[n-k];}private:voidheapify(vector<int>&nums,intsize,inti){intlargest=i;intleft=2*i+1;intright=2*i+2;if(left<size&&nums[left]>nums[largest]){largest=left;}if(right<size&&nums[right]>nums[largest]){largest=right;}if(largest!=i){swap(nums[i],nums[largest]);heapify(nums,size,largest);}}};

5.4 复杂度分析

六、方法四：排序后直接取值

6.1 核心思想

对数组升序排序，然后直接取第 n-k 个元素。

6.2 完整代码

classSolution{public:intfindKthLargest(vector<int>&nums,intk){sort(nums.begin(),nums.end());returnnums[nums.size()-k];}};

6.3 复杂度分析

七、方法五：计数排序（适用于值范围小的场景）

7.1 核心思想

因为nums[i]范围是-10^4到10^4，共 20001 个可能的值。统计每个值出现的次数，然后从最大值开始累加，找到第 k 大的元素。

7.2 算法流程图

数组: [3, 2, 1, 5, 6, 4], k = 2 元素范围: -10^4 ~ 10^4 -> 需要统计 20001 个可能的值 +------------------------------------------------------------+ | 统计每个值出现的次数 | +------------------------------------------------------------+ 遍历数组: 3 -> count[3+offset]++ 2 -> count[2+offset]++ 1 -> count[1+offset]++ 5 -> count[5+offset]++ 6 -> count[6+offset]++ 4 -> count[4+offset]++ 计数数组（部分）: ... 1:1, 2:1, 3:1, 4:1, 5:1, 6:1 ... +------------------------------------------------------------+ | 从最大值开始累加，找到第 k 大的元素 | +------------------------------------------------------------+ 从 6 开始向左累加: count[6] = 1 -> 累加和 = 1 < k(2)，继续 count[5] = 1 -> 累加和 = 2 == k(2) -> 答案 = 5 答案 = 5

7.3 完整代码

classSolution{public:intfindKthLargest(vector<int>&nums,intk){constintOFFSET=10000;// 偏移量，将负数转为正数索引constintRANGE=20001;// -10000 到 10000，共 20001 个值vector<int>count(RANGE,0);// 统计每个值出现的次数for(intnum:nums){count[num+OFFSET]++;}// 从最大值开始累加for(inti=RANGE-1;i>=0;i--){k-=count[i];if(k<=0){returni-OFFSET;}}return0;// 不会走到这里}};

7.4 复杂度分析

八、方法对比总结

时间复杂度对比（假设 n=100000, k=100）： 快速选择: O(n) = 100000 ★最优 小顶堆: O(n log k) = 100000 * 7 ≈ 700000 大顶堆: O(n log n) = 100000 * 17 ≈ 1700000 排序: O(n log n) = 100000 * 17 ≈ 1700000 计数排序: O(n + R) = 100000 + 20001 ≈ 120000 ★（本题最优） 空间复杂度对比： 快速选择: O(1) ★最优 小顶堆: O(k) ★ 大顶堆: O(1) ★ 排序: O(1) ★ 计数排序: O(R) （R=20001）

九、面试追问 FAQ

十、相关题目

十一、总结