堆: 支持动态维护最值的一种数据结构
1.可以用于解决数据流中的一些问题, 数据流这类问题存在一些动态性
347.前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2: 输入: nums = [1], k = 1 输出: [1]
分析:
1.可以用一个 hash 表记录下来每个出现的次数
2.用一个小顶堆 priority_queue
3.遍历 hash 表, 先保留下来前 k 个元素, 假设 map 元素个数小于 k, 那么前 k 个高频的就是已有的元素; 如果新遍历到的元素的出现次数大于堆顶这个出现次数, 淘汰掉当前小顶, 新的元素进入小顶堆; 实质上是永远淘汰最小的出现次数这种迭代思想, 剩下的就是频率最大的 K 个元素了
4.小顶堆的基础元素用 pair
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> value2req;
typedef pair<int, int> pii;
for (auto& x: nums) {
++value2req[x];
}
auto cmp = [] (const pii a, const pii b) {
return a.second > b.second;
};
// 用小顶堆保存 k 个元素, 按照元素出现次数排序
priority_queue<pii, vector<pii>, decltype(cmp)> pq;
for (auto& x: value2req) {
if (pq.size() < k) {
pq.push(make_pair(x.first, x.second));
// 每次淘汰掉最小的出现次数, 并且保留 k 个元素
} else if (pq.size() == k) {
if (x.second > pq.top().second) {
pq.pop();
pq.push(make_pair(x.first, x.second));
}
}
}
vector<int> ans;
while (!pq.empty()) {
ans.push_back(pq.top().first);
pq.pop();
}
return ans;
}
};
703.数据流中的第K大的元素
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。输入：
[“KthLargest”, “add”, “add”, “add”, “add”, “add”]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
分析:
1.因为是数据流, 我们时时刻刻都得维护前 k 个元素, 保持动态性, 所以我们用大顶堆去保存元素
class KthLargest {
private:
priority_queue<int, vector<int>, greater<int>> q;
int k;
public:
KthLargest(int k, vector<int>& nums) {
this->k = k;
for (auto& x : nums) {
add(x);
}
}
int add(int val) {
q.push(val);
if (q.size() > k) {
q.pop();
}
return q.top();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/
295.数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。示例 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
分析:
1.因为是数据流, 所以要保证添加和删除的动态性, 所以用到 堆 这种结构
2.我们用两个堆, 动态地维护大的一半元素和小的一半元素；大于等于中位数的, 称之为 largeHalf, 放入一个小顶堆; 小于中位数的, smallHalf, 放入大顶堆; 维持大集合元素数量大于等于小集合, 如果大集合元素数量更大, 那么直接返回大集合的堆顶; 否则是两个堆顶求和除以 2
3.需要持续保证 largeHalf 里面数量比 smallHalf 多或者相等
class MedianFinder {
private:
priority_queue<int, vector<int>, less<int>> largeHalf;
priority_queue<int, vector<int>, greater<int>> smallHalf;
public:
MedianFinder() {
}
void addNum(int num) {
// 每次先加入到 largeHalf
largeHalf.push(num);
// 迁移 largeHalf中的最小的过去 smallHalf
smallHalf.push(largeHalf.top());
largeHalf.pop();
// 动态维护 largeHalf 数量多于或者等于 smallHalf
if (largeHalf.size() < smallHalf.size()) {
largeHalf.push(smallHalf.top());
smallHalf.pop();
}
}
double findMedian() {
if (largeHalf.size() > smallHalf.size()) {
return largeHalf.top();
}
return (largeHalf.top() + smallHalf.top()) / 2.0;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
转载请注明来源, from goldandrabbit.github.io
