题解 | #数据流中的中位数#
数据流中的中位数
https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1
#include <queue> #include <vector> class Solution { public: priority_queue<int> max_heap; priority_queue<int, vector<int>, std::greater<int>> min_heap; void Insert(int num) { // 大顶堆为空或大顶堆堆顶大于插入元素 if (max_heap.empty() || max_heap.top() > num) { max_heap.push(num); } else { min_heap.push(num); } int min_size = min_heap.size(); int max_size = max_heap.size(); // 检查堆中元素是否相等或者数量相差1 if (max_size - min_size > 1) { int max_top = max_heap.top(); max_heap.pop(); min_heap.push(max_top); } else if (max_size < min_size) { int min_top = min_heap.top(); min_heap.pop(); max_heap.push(min_top); } } double GetMedian() { if (max_heap.size() == min_heap.size()) { return (max_heap.top() + min_heap.top()) /2.0; } return (double)max_heap.top(); } };
堆是首选思路
由于要求中位数
因此, 需要用到两个堆 大顶堆,小顶堆,
同一个元素,如果满足大顶对的条件, 优先插入到大顶堆上面,
否则, 插入小顶堆上;
然后检查两个堆是否平衡,如果不平衡, 将其弹出, 插入小顶堆上;
note_coding 文章被收录于专栏
记录自己的解题思路, 欢迎评价