C++优先队列(大小堆)
数据流中的中位数
http://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1
大致思路如下:
把数据流分成前后两个部分,前一部分的所有值都比后一部分的所有值小;
前一部分用一个最大堆存储,后一部分用一个最小堆存储;
之所以这样是为了方便判断新输入的数应该进入前半部分还是后半部分,如果大于最大堆的堆顶,说明大于前半部分的所有数,因此可以进入后半部分,对后半部分的操作同理;
当输入的数的个数为奇数时,最小堆比最大堆多一个数,直接输出最小堆堆顶的数即可;
当为偶数时,输出两个堆顶数的平均数。
class Solution { private: int cnt = 0; priority_queue<int> max_heap; priority_queue<int, vector<int>, greater<int>> min_heap; public: void Insert(int num) { if((cnt & 1) == 0) { max_heap.push(num); int tmp=max_heap.top(); max_heap.pop(); min_heap.push(tmp); } else { min_heap.push(num); int tmp = min_heap.top(); min_heap.pop(); max_heap.push(tmp); } ++cnt; } double GetMedian() { if((cnt & 1) == 0) return (double)(min_heap.top() + max_heap.top()) / 2.0; else return (double)min_heap.top(); } };