[LeetCode] Find Median from Data Stream-白红宇

[LeetCode] Find Median from Data Stream

阅读量：6592 次

发布时间：2019-06-24

本文共 1094 字，大约阅读时间需要 3 分钟。

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 .

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

, less

> maxH; // stores the smaller half priority_queue

, greater

> minH; // stores the larger half};// Your MedianFinder object will be instantiated and called as such:// MedianFinder mf;// mf.addNum(1); // mf.findMedian();

转载于:https://www.cnblogs.com/jcliBlogger/p/4893468.html