295. Find Median from Data Stream 数据流的中位数

@TOC

# 题目描述

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)
findMedian() -> 1.5
findMedian() -> 2
``````

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

# 解题方法

# 大根堆+小根堆

• 我们如果能排序，就能找到中位数 ==> 排序时间复杂度太高，不可
• 把数据集划分成两部分，一半比中位数小，一半比中位数大 ==> 数据分为两部分
• 只需要知道比中位数小的那部分的最大值和比中位数大的那部分的最小值 ==> 大根堆和小根堆

C++代码如下：

``````class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}

lesser.push(num);
larger.push(lesser.top());
lesser.pop();
if (larger.size() > lesser.size()) {
lesser.push(larger.top());
larger.pop();
}
}

double findMedian() {
return lesser.size() == larger.size() ? (lesser.top() + larger.top()) / 2 : lesser.top();
}
private:
// 存放比中位数小的数字，大根堆
priority_queue<double> lesser;
// 存放比中位数大的数字，小根堆
priority_queue<double, vector<double>, greater<double>> larger;
};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();