295. Find Median from Data Stream

https://leetcode.com/problems/find-median-from-data-stream/

实时找当前data stream中遇到所有元素的中位数。维持排序可以用tree set，即balanced BST。天生root附近即中位数，且找下个比它大的或上一个比它小的只要O(lgN)时间。维持两个指针l和r分别指向中位数的两个候选。根据插入元素后长度变化和num与r大小做分类讨论。

还有可以维持一个max heap存小的半边，min heap存大的半边，两个heap的top即中位数candidate。

思路参考了花花酱的。

/*
 * @lc app=leetcode id=295 lang=cpp
 *
 * [295] Find Median from Data Stream
 *
 * https://leetcode.com/problems/find-median-from-data-stream/description/
 *
 * algorithms
 * Hard (38.20%)
 * Likes:    1380
 * Dislikes: 27
 * Total Accepted:    125K
 * Total Submissions: 326.7K
 * Testcase Example:  '["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]\n[[],[1],[2],[],[3],[]]'
 *
 * Median is the middle value in an ordered integer list. If the size of the
 * list is even, there is no middle value. So the median is the mean of the two
 * middle value.
 * For example,
 * 
 * [2,3,4], the median is 3
 * 
 * [2,3], the median is (2 + 3) / 2 = 2.5
 * 
 * Design a data structure that supports the following two operations:
 * 
 * 
 * void addNum(int num) - Add a integer number from the data stream to the data
 * structure.
 * double findMedian() - Return the median of all elements so far.
 * 
 * 
 * 
 * 
 * Example:
 * 
 * 
 * addNum(1)
 * addNum(2)
 * findMedian() -> 1.5
 * addNum(3) 
 * findMedian() -> 2
 * 
 * 
 * 
 * 
 * Follow up:
 * 
 * 
 * If all integer numbers from the stream are between 0 and 100, how would you
 * optimize it?
 * If 99% of all integer numbers from the stream are between 0 and 100, how
 * would you optimize it?
 * 
 * 
 */
class MedianFinder {
private: 
    multiset<int> m;
    multiset<int>::const_iterator l;
    multiset<int>::const_iterator r;
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if (m.empty()) {
            l = r = m.insert(num);
            return;
        }
        m.insert(num);
        const int N = m.size();
        if (N & 1) {
            // from even to odd
            if (num >= *r) ++l;
            else l = --r;
        } else {
            // from odd to even
            if (num >= *r) ++r;
            else --l;
        }
    }
    
    double findMedian() {
        return ((double)(*l) + (*r)) / 2;
    }
};

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