【力扣Hot 100】堆
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();
*/