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:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
这里需要我们设计一个数据结构,使得我们可以从当前的字符流中获取中位数。
这里采用了两个优先队列来实现。一个优先队列用来存储字符流中较小的一半,另一个用来存储字符流中数值较大的一半。这样当需要获取当前中位数时,就可以根据当前的数值个数选择一个或是两个数的平均值。
private PriorityQueue<Long> minQueue;
private PriorityQueue<Long> maxQueue;
/** initialize your data structure here. */
public MedianFinder () {
minQueue = new PriorityQueue<Long>();
maxQueue = new PriorityQueue<Long>();
}
public void addNum(int num) {
maxQueue.add((long)num);
minQueue.add(-maxQueue.poll());
if(maxQueue.size() < minQueue.size()){
maxQueue.add(-minQueue.poll());
}
}
public double findMedian() {
if(maxQueue.size() > minQueue.size()){
return maxQueue.peek();
}else{
return ( maxQueue.peek() - minQueue.peek() ) / 2.0;
}
}