Two Heaps
本题是实质是如何最快找到最中间的数的数。每次都sort效率很低。
由于中位数实质就是将数组分为两半，比如说左半边a，右半边b，那么计算median只要考虑 a[-1] 和 b[0] 即可 (奇数偶数的情况都类似)。
顺着这个思路想下去，难点就是当新的num到来，如果保证两边数组的性质，即 a[-1] 和 b[0] 都是正确的。
由于别的元素顺序随意，我们可以用两个heap。左半边a，对应大顶堆 max_heap，右半边b，对应小顶堆 min_heap。
当新的num到来时，先加入max_heap更新最大值，把最大值加入min_heap更新最小值。至此最大值和最小值都是正确的。
为了保证对半分，以及方便区分奇数偶数个元素的情况，我们令
max_heap.size() = min_heap.size() (偶数个元素)
max_heap.size() = min_heap.size()+1 (奇数个元素)
在上述更新法则中，我们只要加一个判断，当min_heap的size超过max_heap时，我们把最小元素再放回max_heap即可。
Example1：median = (5+7)/2
Example2：median 5
class MedianFinder { public: /** initialize your data structure here. */ MedianFinder() {} void addNum(int num) { max_q.push(num); min_q.push(max_q.top()); max_q.pop(); if (min_q.size()>max_q.size()){ max_q.push(min_q.top()); min_q.pop(); } } double findMedian() { if (max_q.size()>min_q.size()) return max_q.top(); else return double(max_q.top()+min_q.top())/2; } private: priority_queue<int> max_q; priority_queue<int,vector<int>,greater<int>> min_q; };
时间复杂度：addNum O(logn) findMedian O(1)
Multiset and Two Pointers
由于本题本质是，在容器更新时仍能够找到最中间的元素。我们可以使用二叉搜索树，insert和查找都是logn。
维护两个pointer，一个指向中间偏小的元素，另一个指向偏大的元素。在新加入num时，我们只要维护这两个指针即可，当前的median即两者的均值。
C++中set本质是红黑树，由于可能有重复元素，使用multiset。两个pointer用iterator，具体更新方法如下：
[注意 multiset insert 相同元素是加到最后]
class MedianFinder { public: /** initialize your data structure here. */ MedianFinder() {} void addNum(int num) { if (s.empty()){ l= r = s.insert(num); return; } s.insert(num); if (s.size()%2==1){ if (num>=*r) l=r; else l=--r; }else{ if (num>=*r) ++r; else --l; } } double findMedian() { return double(*l+*r)/2; } private: multiset<int> s; multiset<int>::iterator l; multiset<int>::iterator r; }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
Other Solutions, such as Bucket
https://leetcode.com/problems/find-median-from-data-stream/solution/
LeetCode 295. Find Median from Data Stream
原文：https://www.cnblogs.com/hankunyan/p/11410226.html