题目描述
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?
题意:中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如,[2,3,4] 的中位数是 3,[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
void addNum(int num)
- 从数据流中添加一个整数到数据结构中。
double findMedian()
- 返回目前所有元素的中位数。
进阶:
如果数据流中所有整数都在 0 到 100 范围内,你将如何优化你的算法?
如果数据流中 99% 的整数都在 0 到 100 范围内,你将如何优化你的算法?
算法1
(双顶堆) $O(logn)$
题解:我们可以使用两个堆来解决这个问题,我们使用一个大顶堆保存整个数据流中较小的那一半元素,再使用一个小顶堆保存整个数据流中较大的那一半元素,同时大顶堆堆顶元素小于等于小顶堆堆顶的元素。如果元素总数是奇数的话,我们把多余的那一个元素放在大顶堆中。那么在求中位数的时候,如果元素总数是奇数,那么直接返回大顶堆堆顶元素,如果元素总数是偶数,那么返回两个堆顶元素的平均值。现在问题就转化成如何去维护两个堆的平衡?我们采取如下的策略,每次比较当前元素和大顶堆堆顶元素,如果当前元素小于大顶堆堆顶元素,那么插入到小顶堆中,否则插入到大顶堆中。每次插入后,可能会导致数量不平衡,所以如果插入后哪边的元素过多了,我们将该堆的堆顶元素弹出插入到另一个堆中。
如果所有整数都在0-100之间,那么我们可以采用类似于计数排序的思想,统计每个数字出现了多少次来求中位数。
如果99%的整数都在0-100之间,我们同样可以采用类似计数排序的思想,但是剩余的1%分配给(负无穷,-1]
和[101,正无穷)
两个桶,但是这两个桶的元素是排好序的。
class MedianFinder {
public:
/** initialize your data structure here. */
int cnt = 0,small_cnt = 0,big_cnt = 0;
priority_queue<int> big_q;
priority_queue<int,vector<int>,greater<int> > small_q;
MedianFinder() {
}
void addNum(int num) {
cnt ++;
if(big_q.empty() || big_q.top() >= num)
{
big_q.push(num);
if(big_q.size() > small_q.size() + 1)
{
int t = big_q.top();
big_q.pop();
small_q.push(t);
}
}else
{
small_q.push(num);
if(small_q.size() > big_q.size())
{
int t = small_q.top();
small_q.pop();
big_q.push(t);
}
}
}
double findMedian() {
if(cnt % 2 == 1)
return big_q.top();
else
return (big_q.top() + small_q.top()) * 1.0 / 2;
}
};