首页 > 其他 > 详细

[LeetCode] Find Median from Data Stream

时间:2015-10-20 01:18:29      阅读:1067      评论:0      收藏:0      [点我收藏+]

This post shares a very nice solution using two heaps: a max heap for the smaller half and a min heap for the larger half. The code is rewritten below in C++, simplifying addNum using the logic in Stefan‘s post.

class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        maxH.push(num);
        int t = maxH.top();
        maxH.pop(); minH.push(t);
        int m = maxH.size(), n = minH.size();
        if (n > m) {
            int t = minH.top();
            minH.pop(); maxH.push(t);
        }
    }

    // Returns the median of current data stream
    double findMedian() { 
        int m = maxH.size(), n = minH.size();
        if (!m && !n) return 0.0;
        if (m == n) return (maxH.top() + minH.top()) / 2.0;
        return (m > n) ? maxH.top() : minH.top();
    }
private:
    priority_queue<int, vector<int>, less<int>> maxH;       // stores the smaller half
    priority_queue<int, vector<int>, greater<int>> minH;    // stores the larger half
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1); 
// mf.findMedian();

 

[LeetCode] Find Median from Data Stream

原文:http://www.cnblogs.com/jcliBlogger/p/4893468.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!