【力扣Hot100】堆

1. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 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 <= 105104 <= nums[i] <= 104

题解

非常经典的堆问题，在AcWing里学过类似的。直接套用就可以了。

class Solution { public: // 建大根堆 vector<int> heap; int size = 0; void up(int x) { while(x && (heap[x / 2] < heap[x])) { swap(heap[x], heap[x / 2]); x = x / 2; } } void down(int x) { int t = x; if(x * 2 < size && heap[x * 2] >= heap[t]) t = x * 2; if(x * 2 + 1 < size && heap[x * 2 + 1] >= heap[t]) t = x * 2 + 1; if(t != x) { swap(heap[x], heap[t]); down(t); } } int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); heap = vector<int>(n); for(int i = 0; i < n; i ++ ) { // 插入 heap[size] = nums[i]; up(size); size ++; } for(int i = 0; i < k - 1; i ++ ) { //删除堆顶 swap(heap[0], heap[size - 1]); size --; down(0); } return heap[0]; } }; 2. 前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入:nums = [1,1,1,2,2,3], k = 2 输出:[1,2]

示例 2:

输入:nums = [1], k = 1 输出:[1]

提示：

1 <= nums.length <= 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

**进阶：**你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n **是数组大小。

题解

用c++自带的优先队列来实现堆。

小根堆：priority_queue<PII, vector, greater> heap;

大根堆：priority_queue<PII, vector, less>heap;

pair<int, int> 首先判断第一个元素，再判断第二个元素来排序。

使用unordered_map<int, int> 来存储每个数出现了多少次。

typedef pair<int, int> PII; class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> map; for(int num : nums) { map[num] ++; } priority_queue<PII, vector<PII>, greater<PII> > heap; for(auto& [num, count] : map) { if(heap.size() == k) { if(count > heap.top().first ) { heap.pop(); heap.push({count, num}); } } else { heap.push({count, num}); } } vector<int> ans(k); for(int i = 0; i < k; i ++ ) { ans[i] = heap.top().second; heap.pop(); } return ans; } }; 3. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。void addNum(int num) 将数据流中的整数 num 添加到数据结构中。double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 105 以内的答案将被接受。

示例 1：

输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0

提示:

105 <= num <= 105在调用 findMedian 之前，数据结构中至少有一个元素最多 5 * 104 次调用 addNum 和 findMedian

题解

用两个优先队列，queMax和queMin：

queMax：存比中位数大的数，小根堆，堆顶是堆中最小的数。

queMin：存比中位数小的数，大根堆，堆顶是堆中最大的数。

如果queMax和queMin大小相等，中位数就是二者的平均。如果大小不相等，那么我们需要使得小根堆一定比大根堆更大，把中位数设置为queMin.top()。

因此，需要加入一个数时：

如果堆为空，把数加入到queMin中。如果数比中位数小，把它加入到queMin中，并调整queMin和queMax的大小，使得queMin.size() == queMax.size() 或者 queMin.size() == queMax.size() + 1。否则，把它加入到queMax中，并调整queMin和queMax的大小，使得queMin.size() == queMax.size() 或者 queMin.size() == queMax.size() + 1。

调整大小的方法就是把数更多的那一方的top弹出，弹出的数加入到另一方中。

class MedianFinder { public: priority_queue<int, vector<int>, greater<int> > queMax; priority_queue<int, vector<int>, less<int> > queMin; MedianFinder() { } void addNum(int num) { if(queMin.size() == 0 || num <= findMedian()) { queMin.push(num); if(queMin.size() > queMax.size() + 1) { queMax.push(queMin.top()); queMin.pop(); } } else { queMax.push(num); if(queMax.size() > queMin.size()) { queMin.push(queMax.top()); queMax.pop(); } } } double findMedian() { if(queMax.size() == queMin.size()) { return (queMax.top() + queMin.top()) / 2.0; } else return queMin.top(); } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */