力扣215. 数组中的第K个最大元素
堆排序
- 前言
- 面试中著名的 TopK 排序；
- 常见的解法有冒泡排序、堆排序；
- 更深入的思路可以参考：拜托，面试别再问我TopK了！！！
- 使用了堆排序的算法，关于堆可以参考：堆数据结构的C++实现
- 思路：
- 使用一个 size = k 小顶堆，之后的元素如果大于堆顶，则将堆顶 pop 后，将此元素入堆，遍历完成后，堆顶即为 TopK 元素；
- 使用了 stl 的优先队列数据结构，默认是大顶堆，小顶堆的构造为：
-
std::priority_queue<int, std::vector<int>, std::greater<int>>
-
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {std::priority_queue<int, std::vector<int>, std::greater<int>> pq;int size = nums.size();for (int i = 0; i < size; ++i) {if (i < k) {pq.push(nums[i]);} else {if (nums[i] > pq.top()) {pq.pop();pq.push(nums[i]);}}}return pq.top();}
};