LeetCode 295. Find Median from Data Stream （堆）

题目

求一个数组的中位数，但是这个数组是动态增加的，怎么做呢？可以考虑到用插入排序，每增加一个值，都插入排序一下，最坏的效率是O(n)，查询效率是O(1)
效率太低，会超时。更高明的做法，是维护两个堆，一个是大堆，一个是小堆，大堆的数字都大于小堆里的数字，两个堆的数字均分这个数字。大堆用最小堆实现，小堆用最大堆实现。
当插入一个数，我们把它跟大堆的堆顶，也就大数字里的最小数对比，要是比它大，就入大堆，要是比它小，就入小堆，之后再调整两个堆，保证平均，调整只要比较堆顶的数字即可。

插入效率变成O(logn),查询还是O(1)

class MedianFinder {
public:
    /** initialize your data structure here. */
    multiset<int> m1;
    multiset<int> m2;
    int n=0;
    int len1;
    int len2;
    MedianFinder() {
        m1.clear();
        m2.clear();
        len1=0;
        len2=0;
        
    }
    
    void addNum(int num) {
       
        if(len1==0&&len2==0)
        {
            m1.insert(num);
            len1++;
            n++;
            return;
        }
       
        multiset<int>::iterator it = prev(m1.end());
        if(num < *it)
        {
            m1.insert(num);
            len1++;
        }
        else
        {
            m2.insert(num);
            len2++;
        }
        
        if(len1<len2-1)
        {
            m1.insert(*m2.begin());
            len1++;
            m2.erase(m2.begin());
            len2--;
        }
        
        if(len1-1>len2)
        {
            m2.insert(*prev(m1.end()));
            len2++;
            m1.erase(prev(m1.end()));
            len1--;
        }
        
        n++;
    }
    
    double findMedian() {
        
        if(n&1)
        {
            if(len1<len2)
                return *m2.begin();
            else
                return *prev(m1.end());
        }
        else
            return 1.0*(*prev(m1.end())+*m2.begin())/2;
        
    }
};

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

LeetCode 295. Find Median from Data Stream （堆）

原文：https://www.cnblogs.com/dacc123/p/12968397.html