LeetCode Find Median from Data Stream

Description:

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.

Solution:

This problem's solution is a little big tricky.

I use two PriorityQueue to implement this. I try to do this on my own, but a little bit hard. So we can use a very interesting way in PriorityQueue.

When we want to add a number, we can first put it into the smaller priority queue, then get the biggest one, and then put this biggest one, and add it into the bigger priority queue.

<span style="font-size:18px;">import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;

class MedianFinder {
	PriorityQueue<Integer> smaller = new PriorityQueue<Integer>(
			new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return o2 - o1;
				}
			});
	PriorityQueue<Integer> bigger = new PriorityQueue<Integer>();

	// Adds a number into the data structure.
	public void addNum(int num) {
		smaller.add(num);
		num = smaller.poll();
		bigger.add(num);
		if (bigger.size() > smaller.size())
			smaller.add(bigger.poll());
	}

	// Returns the median of current data stream
	public double findMedian() {
		if (smaller.size() > bigger.size())
			return smaller.peek();
		else
			return 1.0 * (smaller.peek() + bigger.peek()) / 2;
	}

};

class Solution {
	public static void main(String[] args) {
		MedianFinder mf = new MedianFinder();
		mf.addNum(1);
		mf.addNum(-2);
		mf.addNum(-3);
		mf.addNum(-4);
		System.out.println(mf.findMedian());
		mf.addNum(-5);
		System.out.println(mf.findMedian());
	}
}</span>