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

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?


法一

开两个stl的优先队列-maxheap。small放前一半大的数,large放后一半大的数。
为了让他们的顺序从小到大不变,small的用原数存,large的用负数存。
增删O(logn),查找O(1)
细节:
1.如果是奇数大小,small.top()就是要求的中位数。如果是偶数,(small.top()-large.top())/2就是中位数,是减不是加
2.优先队列的类型是long. -2^31 (which negated is itself, when using 32-bit ints), I use integer types larger than 32 bits.
3.(small.top()-large.top())/2.0。要除以2.0,否则返回的是整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MedianFinder {
private:
std::priority_queue<long> small,large;

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

void addNum(int num) {
small.push(num);//O(logn)

large.push(-small.top());//O(logn)
small.pop();//O(logn)

//保证small大于或者等于large的个数
if(small.size()<large.size())
{
small.push(-large.top());
large.pop();
}
}

double findMedian() {
return small.size()>large.size()? small.top():(small.top()-large.top())/2.0;
}
};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/

法二

开两个stl的优先队列-maxheap和minheap,用来存前后一半的数
细节:
1.如果num小于maxheap.top(),说明在num小的那一半里,放入最大堆,如果不这样的话,可能会排序失败。
2.假定maxheap永远大于或者等于minheap的数量,这样如果两个堆相等就是平均值。不相等就是maxheap.top
3.利用AVL的思想,保证两个堆的深度之差不超过1,如果超过1,就把max堆顶放入min堆中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class MedianFinder {
private:
priority_queue<long> maxheap;
priority_queue<long, vector<long>, greater<long>> minheap;

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

void addNum(int num) {
//细节:如果num小于maxheap.top(),说明在num小的那一半里,放入最大堆,如果不这样的话,可能会排序失败。
if (maxheap.size() == 0 || num < maxheap.top())
{
maxheap.push(num);
}
else
minheap.push(num);
//平衡二叉树
if (minheap.size()> maxheap.size())
{
maxheap.push(minheap.top());
minheap.pop();
}
else if (maxheap.size()>1 + minheap.size())
{
minheap.push(maxheap.top());
maxheap.pop();
}
}

double findMedian() {
return maxheap.size()>minheap.size() ? maxheap.top() : (maxheap.top() + minheap.top()) / 2.0;
}
};
Thanks for Support.