Find Median from Data Stream leetcode 295

题目大意：数据流中不断加入新的整型元素，求已有数据的中位数。

这种问题和求数组中最大k个值类似，至少需要求最大的n/2个数。下面是一种折半插入的算法。

class MedianFinder {
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        auto low = h.begin();
        auto high = h.end();
        auto mid = h.begin();
        while (low < high) { 
            mid = low + (high - low) / 2;  
            if (num < *mid)
                high = mid;
            else
                low = mid + 1;
        }
        h.insert(high, num);
    }
    // Returns the median of current data stream
    double findMedian() {
        int s = h.size();
        if(0 == s) return -1;
        double median(0);
        if (s % 2 == 0) {
            median = (h[s/2] + h[s/2-1]) / 2.0;
        } else {
            median = (double) h[s/2];
        }
        return median;
    }
private:
    vector<int>h;
};
           

折半插入需要的时间貌似多一些。

还有一种用最大堆最小堆的算法，记得剑指offer和lintcode已经有题目了。原理就是将比较小的数字放入最大堆中，较大的数字放入最小堆中，保持两个堆的数据个数相等，如果奇数个数据，就把多出来的放进最小堆中。这样奇数的情况下，最小堆中的堆顶就是中位数，偶数就把两个堆的堆顶求一下平均。

AC code:

class MedianFinder {
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        if(((minHeap.size() + maxHeap.size()) & 1) == 0) {   // 偶数，最小堆需要加入新的值 
            if(maxHeap.size() > 0 && num < maxHeap.top()) {  // 将最大堆的堆顶移到最小堆
                maxHeap.push(num);
                num = maxHeap.top();
                maxHeap.pop();
            }
            minHeap.push(num);
        }
        else {                                              // 奇数，最大堆需要加入新的值
            if(minHeap.size() > 0 && num > minHeap.top()) { // 将最小堆的堆顶移到最大堆
                minHeap.push(num);
                num = minHeap.top();
                minHeap.pop();
            }
            maxHeap.push(num); 
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        int size = minHeap.size() + maxHeap.size();
        if(size == 0) { return -1; }
        double median = 0;
        if((size & 1) != 0) {
            median = (double) minHeap.top();
        }
        else {
            median = (double)(maxHeap.top()+ minHeap.top()) / 2;
        }
        return median;
    }
private:
    priority_queue<int> maxHeap;
    priority_queue<int, std::vector<int>, std::greater<int> > minHeap;
};