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

[LeetCode] Find Median from Data Stream

阅读量：5973 次

发布时间：2019-06-19

本文共 1039 字，大约阅读时间需要 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();

转载地址：http://cqdox.baihongyu.com/

你可能感兴趣的文章