# Lintcode: Data Stream Median

#### Data Stream Median

Numbers keep coming, return the median of numbers at every time a new number added.

Example

For numbers coming list: `[1, 2, 3, 4, 5]`, return `[1, 1, 2, 2, 3]`.

For numbers coming list: `[4, 5, 1, 3, 2, 6, 0]`, return `[4, 4, 4, 3, 3, 3, 3]`.

For numbers coming list: `[2, 20, 100]`, return `[2, 2, 20]`.

Challenge

Total run time in O(nlogn).

Clarification

What’s the definition of Median? – Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is `A[(n - 1) / 2]`. For example, if `A=[1,2,3]`, median is `2`. If `A=[1,19]`, median is `1`.

Solution: 维护两个堆 左边是max heap右边是min heap。当有新的数进来时先比较两个heap的数量 永远让left和right的size一样或者left比right多1， 这样的话median永远是left.poll()。然后确定好应该加到哪个heap之后，要比较当前数和两个堆顶数的大小，来决定是直接把该数放到那个heap中还是应该把另外一个heap的root放过来然后把这个数放到另外那个堆里。

O(NlogN) time.

```public int[] medianII(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int initialSize = 20;
int[] median = new int[nums.length];
Queue < Integer > leftHeap = new PriorityQueue < > (initialSize,
new Comparator < Integer > () {
public int compare(Integer a, Integer b) {
return b - a;
}
});
Queue < Integer > rightHeap = new PriorityQueue < > ();

for (int i = 0; i < nums.length; i++) {
if (leftHeap.size() > rightHeap.size()) {
//need to put this one to rightHeap
if (nums[i] >= leftHeap.peek()) {
rightHeap.offer(nums[i]);
} else {
rightHeap.offer(leftHeap.poll());
leftHeap.offer(nums[i]);
}
} else {
//need to put this one to leftHeap
if (leftHeap.isEmpty() && rightHeap.isEmpty()) {
leftHeap.offer(nums[i]);
} else {
if (nums[i] <= rightHeap.peek()) {
leftHeap.offer(nums[i]);
} else {
leftHeap.offer(rightHeap.poll());
rightHeap.offer(nums[i]);
}
}
}
median[i] = leftHeap.peek();
}
return median;
}```
Share