一、题目描述给定整数数组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二、解题思路总览方法时间复杂度空间复杂度说明排序后直接取值O(n log n)O(1)排序后直接取第 n-k 个元素堆排序大顶堆O(n log n)O(1)建堆 逐个弹出直到第 k 个小顶堆优化O(n log k)O(k)维护大小为 k 的堆适合大数据流快速选择O(n)O(1)基于 partition 的选择算法计数排序O(n R)O®R数值范围适合元素值范围小的场景三、方法一快速选择推荐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-- - i3,j2 | | 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] 43.3 完整代码classSolution{public:intpartition(vectorintnums,intleft,intright){// 随机选择 pivot避免最坏情况intileftrand()%(right-left1);intpivotnums[i];swap(nums[i],nums[left]);ileft1;intjright;while(1){while(ijnums[i]pivot){i;}while(ijnums[j]pivot){j--;}if(ij)break;swap(nums[i],nums[j]);i;j--;}swap(nums[left],nums[j]);returnj;}intfindKthLargest(vectorintnums,intk){srand(time(NULL));intnnums.size();inttarget_indexn-k;intleft0,rightn-1;while(true){intipartition(nums,left,right);if(itarget_index){returnnums[i];}if(itarget_index){righti-1;}else{lefti1;}}}};3.4 复杂度分析情况时间复杂度说明平均O(n)每次 partition 大致将问题规模减半最坏O(n^2)pivot 选择不当有序数组选最小值空间复杂度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 ------------------------------------------------------------ | 初始化小顶堆大小限制为 k2 | ------------------------------------------------------------ 遍历元素: ------------------------------------------------------------ | 插入 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(vectorintnums,intk){priority_queueint,vectorint,greaterintminHeap;for(intnum:nums){minHeap.push(num);if(minHeap.size()k){minHeap.pop();}}returnminHeap.top();}};4.4 复杂度分析复杂度值说明时间O(n log k)n 个元素每个入堆 O(log k)空间O(k)堆的大小五、方法三大顶堆 弹出5.1 核心思想将整个数组建成大顶堆然后弹出 k 次堆顶最后一次弹出的就是第 k 大的元素。5.2 算法流程图数组: [3, 2, 1, 5, 6, 4], k 2 ------------------------------------------------------------ | Step 1: 建大顶堆从最后一个非叶子节点开始下沉 | ------------------------------------------------------------ 初始数组完全二叉树: 3 / \ 2 1 / \ / 5 6 4 下沉 i2 (节点2): 3 / \ 6 1 / \ / 5 2 4 下沉 i1 (节点3): 6 / \ 5 4 / \ / 3 2 1 下沉 i0 (节点6): 6 / \ 5 4 / \ / 3 2 1 ------------------------------------------------------------ | Step 2: 弹出堆顶 k2 次 | ------------------------------------------------------------ 第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(vectorintnums,intk){intnnums.size();// 建大顶堆for(intin/2-1;i0;i--){heapify(nums,n,i);}// 弹出 k 次for(inti0;ik;i){swap(nums[0],nums[n-1-i]);heapify(nums,n-1-i,0);}returnnums[n-k];}private:voidheapify(vectorintnums,intsize,inti){intlargesti;intleft2*i1;intright2*i2;if(leftsizenums[left]nums[largest]){largestleft;}if(rightsizenums[right]nums[largest]){largestright;}if(largest!i){swap(nums[i],nums[largest]);heapify(nums,size,largest);}}};5.4 复杂度分析复杂度值说明时间O(n log n)建堆 O(n) 弹出 k 次 O(k log n)空间O(1)原地调整六、方法四排序后直接取值6.1 核心思想对数组升序排序然后直接取第 n-k 个元素。6.2 完整代码classSolution{public:intfindKthLargest(vectorintnums,intk){sort(nums.begin(),nums.end());returnnums[nums.size()-k];}};6.3 复杂度分析复杂度值说明时间O(n log n)排序的时间复杂度空间O(1)若使用原地排序七、方法五计数排序适用于值范围小的场景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[3offset] 2 - count[2offset] 1 - count[1offset] 5 - count[5offset] 6 - count[6offset] 4 - count[4offset] 计数数组部分: ... 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 答案 57.3 完整代码classSolution{public:intfindKthLargest(vectorintnums,intk){constintOFFSET10000;// 偏移量将负数转为正数索引constintRANGE20001;// -10000 到 10000共 20001 个值vectorintcount(RANGE,0);// 统计每个值出现的次数for(intnum:nums){count[numOFFSET];}// 从最大值开始累加for(intiRANGE-1;i0;i--){k-count[i];if(k0){returni-OFFSET;}}return0;// 不会走到这里}};7.4 复杂度分析复杂度值说明时间O(n R)n数组长度R数值范围(20001)空间O®计数数组大小八、方法对比总结方法时间复杂度空间复杂度适用场景快速选择O(n) 平均O(1)通用场景要求 O(n) 时首选小顶堆O(n log k)O(k)大数据流TOP-K 问题大顶堆O(n log n)O(1)需要完整排序时排序后取值O(n log n)O(1)简单直接代码简洁计数排序O(n R)O®值范围小如本题 -104~104时间复杂度对比假设 n100000, k100 快速选择: 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) R20001九、面试追问 FAQ问题回答Q: 快速选择为什么是 O(n) 而不是 O(n log n)因为每次 partition 只递归一边T(n) n n/2 n/4 … 2n O(n)Q: 快速选择最坏情况是什么有序数组 每次选最小/最大 pivot退化为 O(n^2)。解决方法是随机选择 pivotQ: 小顶堆和大顶堆的选择TOP-K 问题用小顶堆维护 k 个最大全部排序用大顶堆Q: 为什么快速选择空间是 O(1)原地 partition只用几个指针变量。递归栈深度 O(log n)不算额外空间Q: 计数排序的限制只能用于值范围有限的整数排序且范围不能太大Q: 稳定性的考虑本题不要求稳定性。堆排序不稳定快速选择也不稳定十、相关题目题目难度关键点215. 数组中的第K个最大元素中等快速选择 / 堆排序347. 前 K 个高频元素中等桶排序 / 堆排序703. 数据流中的第 K 大元素简单小顶堆973. 最接近原点的 K 个点中等堆排序 / 快速选择十一、总结要点说明核心思想求第 K 大 - 转换为求下标 n-k 的元素快速选择平均 O(n)随机 pivot 避免退化小顶堆O(n log k)适合大数据流 TOP-K选择依据根据数据规模和值范围选择合适方法
【力扣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二、解题思路总览方法时间复杂度空间复杂度说明排序后直接取值O(n log n)O(1)排序后直接取第 n-k 个元素堆排序大顶堆O(n log n)O(1)建堆 逐个弹出直到第 k 个小顶堆优化O(n log k)O(k)维护大小为 k 的堆适合大数据流快速选择O(n)O(1)基于 partition 的选择算法计数排序O(n R)O®R数值范围适合元素值范围小的场景三、方法一快速选择推荐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-- - i3,j2 | | 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] 43.3 完整代码classSolution{public:intpartition(vectorintnums,intleft,intright){// 随机选择 pivot避免最坏情况intileftrand()%(right-left1);intpivotnums[i];swap(nums[i],nums[left]);ileft1;intjright;while(1){while(ijnums[i]pivot){i;}while(ijnums[j]pivot){j--;}if(ij)break;swap(nums[i],nums[j]);i;j--;}swap(nums[left],nums[j]);returnj;}intfindKthLargest(vectorintnums,intk){srand(time(NULL));intnnums.size();inttarget_indexn-k;intleft0,rightn-1;while(true){intipartition(nums,left,right);if(itarget_index){returnnums[i];}if(itarget_index){righti-1;}else{lefti1;}}}};3.4 复杂度分析情况时间复杂度说明平均O(n)每次 partition 大致将问题规模减半最坏O(n^2)pivot 选择不当有序数组选最小值空间复杂度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 ------------------------------------------------------------ | 初始化小顶堆大小限制为 k2 | ------------------------------------------------------------ 遍历元素: ------------------------------------------------------------ | 插入 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(vectorintnums,intk){priority_queueint,vectorint,greaterintminHeap;for(intnum:nums){minHeap.push(num);if(minHeap.size()k){minHeap.pop();}}returnminHeap.top();}};4.4 复杂度分析复杂度值说明时间O(n log k)n 个元素每个入堆 O(log k)空间O(k)堆的大小五、方法三大顶堆 弹出5.1 核心思想将整个数组建成大顶堆然后弹出 k 次堆顶最后一次弹出的就是第 k 大的元素。5.2 算法流程图数组: [3, 2, 1, 5, 6, 4], k 2 ------------------------------------------------------------ | Step 1: 建大顶堆从最后一个非叶子节点开始下沉 | ------------------------------------------------------------ 初始数组完全二叉树: 3 / \ 2 1 / \ / 5 6 4 下沉 i2 (节点2): 3 / \ 6 1 / \ / 5 2 4 下沉 i1 (节点3): 6 / \ 5 4 / \ / 3 2 1 下沉 i0 (节点6): 6 / \ 5 4 / \ / 3 2 1 ------------------------------------------------------------ | Step 2: 弹出堆顶 k2 次 | ------------------------------------------------------------ 第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(vectorintnums,intk){intnnums.size();// 建大顶堆for(intin/2-1;i0;i--){heapify(nums,n,i);}// 弹出 k 次for(inti0;ik;i){swap(nums[0],nums[n-1-i]);heapify(nums,n-1-i,0);}returnnums[n-k];}private:voidheapify(vectorintnums,intsize,inti){intlargesti;intleft2*i1;intright2*i2;if(leftsizenums[left]nums[largest]){largestleft;}if(rightsizenums[right]nums[largest]){largestright;}if(largest!i){swap(nums[i],nums[largest]);heapify(nums,size,largest);}}};5.4 复杂度分析复杂度值说明时间O(n log n)建堆 O(n) 弹出 k 次 O(k log n)空间O(1)原地调整六、方法四排序后直接取值6.1 核心思想对数组升序排序然后直接取第 n-k 个元素。6.2 完整代码classSolution{public:intfindKthLargest(vectorintnums,intk){sort(nums.begin(),nums.end());returnnums[nums.size()-k];}};6.3 复杂度分析复杂度值说明时间O(n log n)排序的时间复杂度空间O(1)若使用原地排序七、方法五计数排序适用于值范围小的场景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[3offset] 2 - count[2offset] 1 - count[1offset] 5 - count[5offset] 6 - count[6offset] 4 - count[4offset] 计数数组部分: ... 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 答案 57.3 完整代码classSolution{public:intfindKthLargest(vectorintnums,intk){constintOFFSET10000;// 偏移量将负数转为正数索引constintRANGE20001;// -10000 到 10000共 20001 个值vectorintcount(RANGE,0);// 统计每个值出现的次数for(intnum:nums){count[numOFFSET];}// 从最大值开始累加for(intiRANGE-1;i0;i--){k-count[i];if(k0){returni-OFFSET;}}return0;// 不会走到这里}};7.4 复杂度分析复杂度值说明时间O(n R)n数组长度R数值范围(20001)空间O®计数数组大小八、方法对比总结方法时间复杂度空间复杂度适用场景快速选择O(n) 平均O(1)通用场景要求 O(n) 时首选小顶堆O(n log k)O(k)大数据流TOP-K 问题大顶堆O(n log n)O(1)需要完整排序时排序后取值O(n log n)O(1)简单直接代码简洁计数排序O(n R)O®值范围小如本题 -104~104时间复杂度对比假设 n100000, k100 快速选择: 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) R20001九、面试追问 FAQ问题回答Q: 快速选择为什么是 O(n) 而不是 O(n log n)因为每次 partition 只递归一边T(n) n n/2 n/4 … 2n O(n)Q: 快速选择最坏情况是什么有序数组 每次选最小/最大 pivot退化为 O(n^2)。解决方法是随机选择 pivotQ: 小顶堆和大顶堆的选择TOP-K 问题用小顶堆维护 k 个最大全部排序用大顶堆Q: 为什么快速选择空间是 O(1)原地 partition只用几个指针变量。递归栈深度 O(log n)不算额外空间Q: 计数排序的限制只能用于值范围有限的整数排序且范围不能太大Q: 稳定性的考虑本题不要求稳定性。堆排序不稳定快速选择也不稳定十、相关题目题目难度关键点215. 数组中的第K个最大元素中等快速选择 / 堆排序347. 前 K 个高频元素中等桶排序 / 堆排序703. 数据流中的第 K 大元素简单小顶堆973. 最接近原点的 K 个点中等堆排序 / 快速选择十一、总结要点说明核心思想求第 K 大 - 转换为求下标 n-k 的元素快速选择平均 O(n)随机 pivot 避免退化小顶堆O(n log k)适合大数据流 TOP-K选择依据根据数据规模和值范围选择合适方法
