295-数据流的中位数

LeetCode 295. Find Median from Data Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within $10^{-5}$ of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

method

将数据分成两半，用两个堆来存储

• 大根堆存储小于等于中位数的数，可以快速获得最大值

• 小根堆存储大于中位数的数，可以快速获得最小值

• 如果是奇数个，大根堆的元素会比小根堆的多一个，中位数就是大根堆的堆顶

• 如果是偶数个，中位数就是(前一半的最大值+后一半的最小值) / 2

始终要保持前一半和后一半相等或多一个

• 如果当前元素比前一半的最大值小，就放到前一半，如果放进来后前一半的数量大于后一半加1，要把最大值移到后一半
• 否则放到后一半，如果放进来后数量比前一半多，就要把最小值移到前一半

priority_queue<int, vector<int>, less<int>> qMin;
priority_queue<int, vector<int>, greater<int>> qMax;
MedianFinder() {}

void addNum(int num) {
    if (qMin.empty() || num < qMin.top()) { // 放前一半
        qMin.push(num);
        if (qMin.size() > qMax.size() + 1) {    // 多了移到后一半
            qMax.push(qMin.top());
            qMin.pop();
        }
    }
    else {  // 放后一半
        qMax.push(num);
        if (qMax.size() > qMin.size()) {    // 多了移动前一半
            qMin.push(qMax.top());
            qMax.pop();
        }
    }
}

double findMedian() {
    if (qMin.size() == qMax.size()) {   // 相等就是两个相加除2
        return (qMin.top() + qMax.top()) / 2.0;
    }
    else return qMin.top(); // 不相等就是前一半的最大值
}