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;
}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *