Find Median from Data Stream解题报告

Description:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Link:

https://leetcode.com/problems/find-median-from-data-stream/description/

解题方法：

使用因为这个数据结构只需要找中位数，不需要pop，所以我们可以使用一个maxheap和一个minheap来储存数据。按照从小到大，maxheap存左半部分数据，minheap存右半部分数据。
当加入新的数时，如果两个heap的size相同，那么加到左边；否则加到右边。此时可能会发生两种特殊情况。

• 在加入左边时，这个数比右边堆顶的数还要大，这时要把右边堆顶的数加入到左边，而右边堆顶pop，将要加入的数push到右边堆去。（总体左边堆还是多了个数，右边堆size不变）
• 在加入右边时，这个数比左边堆顶的数还要小，这时要把左边堆顶的数加入到右边，而左边pop堆顶，将要加入的数push到左边去。（总体右边多了一个数，而左边的size不变）

Tips:

最后算mean的时候，注意除数要用2.0这种double而不是int。

Time Complexity：

插入O(logn)
取中位数O(1)

完整代码：

class MedianFinder 
{
public:
    /** initialize your data structure here. */
    MedianFinder() 
    {
        
    }
    
    void addNum(int num) 
    {
        if(left.size() == right.size())
        {
            if(right.size() && num > right.top())
            {
                left.push(right.top());
                right.pop();
                right.push(num);
            }
            else
            {
                left.push(num);
            }
        }
        else
        {
            if(num < left.top())
            {
                right.push(left.top());
                left.pop();
                left.push(num);
            }
            else
            {
                right.push(num);
            }
        }
    }
    
    double findMedian() 
    {
        return left.size() > right.size() ? left.top() : ((left.top() + right.top()) / 2.0);
    }
private:
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int>> right;
};