学步园

题目

原文：

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

译文：

随机产生一些数据，并传递给一个方法，写一个程序找出并维护这些数的中位数。

解答

ctci解法：

一个解决的方法是使用两个优先堆：一个最大堆存储比中位数小一点的值，最小堆存储比中位数大的值，这样中位数就是最大堆的最大值；当一个新的的值到达时，如果它小于或等于中位值则放在堆的下面，否则放在堆的上面。这堆的大小是等于小于堆的额外大小。这样容易通过从一个堆到另一个堆上移元素来被存储。这样中位值是可以达到的更新时间为O(lgn)

代码如下：

private Comparator<Integer> maxHeapComparator, minHeapComparator;
private PriorityQueue<Integer> maxHeap, minHeap;
public void addNewNumber(int randomNumber) {
	if (maxHeap.size() == minHeap.size()) {
		if ((minHeap.peek() != null) &&randomNumber > minHeap.peek()) {
			maxHeap.offer(minHeap.poll());
			minHeap.offer(randomNumber);
		} else {
			maxHeap.offer(randomNumber);
		}
	}else {
		if(randomNumber < maxHeap.peek()){
			minHeap.offer(maxHeap.poll());
			maxHeap.offer(randomNumber);
		}else {
			minHeap.offer(randomNumber);
		}
	}
}
public static double getMedian() {
	if (maxHeap.isEmpty()) return minHeap.peek();
	else if (minHeap.isEmpty()) return maxHeap.peek();
	if (maxHeap.size() == minHeap.size()) {
		return (minHeap.peek() + maxHeap.peek()) / 2;
	} else if (maxHeap.size() > minHeap.size()) {
		return maxHeap.peek();
	} else {
		return minHeap.peek();
	}
}

---EOF---