295. Find Median from Data Stream

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.

Examples:

[2,3,4], the median is3

[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.

For example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

S: 维护两个heap (nlogn) n为插入元素次数

如果只用找一次median排序就可以解决，但是要找多次就不合适排序，否则复杂度变成n*nlogn。

因为median左边元素都小于它，右边元素都大于它，考虑左边维护一个最大堆left，右边维护一个最小堆right，保证

left.size() >= right.size(). median一定是left.top或者(left.top + right.top)/2

lass MedianFinder {
public:
    void addNum(int num) {
        if (left.empty() || left.top() >= num) {
            left.push(num);
        } else {
            right.push(num);
        }
        if (left.size() - 1 > right.size()) {
            int top = left.top();
            left.pop();
            right.push(top);
        } else if (left.size() < right.size()) {
            int top = right.top();
            right.pop();
            left.push(top);
        }        
    }

    double findMedian() {
        double result;
        if (left.size() > right.size()) {
            result = left.top();
        } else {
            result = left.top() + (right.top() - left.top()) / 2.0; 
        }
        return result;
    }

private:
    priority_queue<int> left;  //maxheap, top element is the median
    priority_queue<int, vector<int>, greater<int>> right;  //minheap
};

480. Sliding Window Median

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.

Examples:

[2,3,4], the median is3

[2,3], the median is(2 + 3) / 2 = 2.5

Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Give n nums=[1,3,-1,-3,5,3,6,7], and k= 3.

S1: two hashheap (STL:: multiset) 和上题一样维护一个最大堆和一个最小堆

S2: one sorted set O(nlogk)

用multiset维护一个长为k的window，median指向widow的第k/2位，每次加入、删除元素时更新median的位置

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    multiset<int> window(nums.begin(), nums.begin() + k);
    auto mid = next(window.begin(), k / 2);
    vector<double> medians;
    for (int i=k; ; i++) {

        // Push the current median.
        medians.push_back((double(*mid) + *next(mid, k%2 - 1)) / 2);

        // If all done, return.
        if (i == nums.size())
            return medians;

        // Insert nums[i].
        window.insert(nums[i]);
        if (nums[i] < *mid)
            mid--;

        // Erase nums[i-k].
        if (nums[i-k] <= *mid)
            mid++;
        window.erase(window.lower_bound(nums[i-k]));
    }
}