Find Median from Data Stream

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就是有一半数目的数字大于它,一般书目的数字小于它。于是:用两个Heap:一个MaxHeap(最顶上是最大值)来存小于median的那一半数字;一个MinHeap(最顶上是最小值)来存大于median的那一半数字。在addNumber的过程中需要保持这两个heap的size相差不超过1.

最精简的写法不会写而且我目前也不太好理解,于是就先写了很多if else的。

 

 

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: