Find Median from Data Stream leetcode 295

題目大意：資料流中不斷加入新的整型元素，求已有資料的中位數。

這種問題和求數組中最大k個值類似，至少需要求最大的n/2個數。下面是一種折半插入的算法。

class MedianFinder {
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        auto low = h.begin();
        auto high = h.end();
        auto mid = h.begin();
        while (low < high) { 
            mid = low + (high - low) / 2;  
            if (num < *mid)
                high = mid;
            else
                low = mid + 1;
        }
        h.insert(high, num);
    }
    // Returns the median of current data stream
    double findMedian() {
        int s = h.size();
        if(0 == s) return -1;
        double median(0);
        if (s % 2 == 0) {
            median = (h[s/2] + h[s/2-1]) / 2.0;
        } else {
            median = (double) h[s/2];
        }
        return median;
    }
private:
    vector<int>h;
};
           

折半插入需要的時間貌似多一些。

還有一種用最大堆最小堆的算法，記得劍指offer和lintcode已經有題目了。原理就是将比較小的數字放入最大堆中，較大的數字放入最小堆中，保持兩個堆的資料個數相等，如果奇數個資料，就把多出來的放進最小堆中。這樣奇數的情況下，最小堆中的堆頂就是中位數，偶數就把兩個堆的堆頂求一下平均。

AC code:

class MedianFinder {
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        if(((minHeap.size() + maxHeap.size()) & 1) == 0) {   // 偶數，最小堆需要加入新的值 
            if(maxHeap.size() > 0 && num < maxHeap.top()) {  // 将最大堆的堆頂移到最小堆
                maxHeap.push(num);
                num = maxHeap.top();
                maxHeap.pop();
            }
            minHeap.push(num);
        }
        else {                                              // 奇數，最大堆需要加入新的值
            if(minHeap.size() > 0 && num > minHeap.top()) { // 将最小堆的堆頂移到最大堆
                minHeap.push(num);
                num = minHeap.top();
                minHeap.pop();
            }
            maxHeap.push(num); 
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        int size = minHeap.size() + maxHeap.size();
        if(size == 0) { return -1; }
        double median = 0;
        if((size & 1) != 0) {
            median = (double) minHeap.top();
        }
        else {
            median = (double)(maxHeap.top()+ minHeap.top()) / 2;
        }
        return median;
    }
private:
    priority_queue<int> maxHeap;
    priority_queue<int, std::vector<int>, std::greater<int> > minHeap;
};