LeetCode 295. Find Median from Data Stream

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.For example,

[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

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

解析：在数据流中获取到数组的中位数，首先这里是数据流的形式，另外，中位数是需要对数据流进行排序，然后获取到中间数值。如果有奇数个数字，则返回中间的数字；如果有偶数个数字，则返回中间两个数字的平均值。

解法1：

采用一个vector存放数据流，每来一个数字，则进行插入排序，最终保证数组是有序的。具体代码如下：

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        nums.clear();
        median = 0;
    }
    
    void addNum(int num) {
        auto it = nums.begin();
        for(; it != nums.end(); it++)
        {
            if(*it > num)
            {
                break;
            }
        }
        nums.insert(it, num);
    }
    
    double findMedian() {
        int size = nums.size();
        if(size%2==1)
            return nums[size/2];
        else
            return (nums[size/2-1] + nums[size/2])/2.0;
    }
    vector<int> nums;
    int median;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

耗时952ms，还是耗时比较多的。

解法2：

采用堆的思路，定义两个堆small和large，分别存放有序数组的前半部分和后半部分。需要注意的是small是存在由大到小的数值，top位置是前半部分最大的；large存放的是由小到大的数值，最小的在top，这样取中位数的时候比较方便。具体代码如下：

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        small.push(num);
        large.push(small.top());
        small.pop();
        if(small.size() < large.size())
        {
            small.push(large.top());
            large.pop();
        }
    }
    
    double findMedian() {
        return small.size() > large.size() ?small.top():0.5*(small.top() + large.top());
        
    }
    priority_queue<long> small;
    priority_queue<long, vector<long>, greater<long> > large;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

耗时情况如下：