Find Median from Data Stream/Sliding Window Median

Leave a comment

December 1, 2016 by oneOokay

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

For example:

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

首先要了解什么是median:median就是有一半数目的数字>=它,一半数目的数字<=它。

这题只要理解了median的实际意义就还挺好做.

于是:用两个Heap:一个MaxHeap(最顶上是最大值)来存小于median的那一半数字 left;一个MinHeap(最顶上是最小值)来存大于median的那一半数字 right。在addNumber的过程中需要保持这两个heap的size相差不超过1. (确认一下你想要哪一个heap为多1的那个heap,就当计算median的时候,如果两个heap不等直接从size大的heap里面peek的value就是median.)我是用right作为多一个的heap.

另外naming方面 left和right比较不容搞混淆,比max和min好一些.

最精简的写法就是不管怎样都先放到一个heap里面倒腾一下,取出来,放到另外一个heap里面,然后如果size()不满足条件的话,再倒腾一下. 我觉得没必要..

private PriorityQueue left;
private PriorityQueue right;
public MedianFinder() {
left  = new PriorityQueue(Collections.reverseOrder());
right = new PriorityQueue();
}

public void addNum(int num) {
if (left.isEmpty() || num >= left.peek()){
right.offer(num);
if(right.size() > left.size() + 1){
left.offer(right.poll());
}
}else{
left.offer(num);
if(left.size() > right.size()){
right.offer(left.poll());}}}

public double findMedian() {
if (left.isEmpty() && right.isEmpty()) return 0.0;
if (left.size() < right.size()) return (double) right.peek();
return (left.peek() + right.peek())/ 2.0;
}

Sliding Window Median:

用Find Median from Data Stream类似的两个heap,但是如何remove?似乎效率不高.

因为我不知道heap有一个remove() method. remove(obj) 会返回一个boolean值.

最终注意一下相加sum overflow的问题就可以了.

overflow不能只定义sum为long,要把相加的数先转化为long,再相加.

long sum = (long)left.peek() + (long)right.peek();

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: