title
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
solution
public class Solution {
private PriorityQueue<Integer> minP=new PriorityQueue<>();
private PriorityQueue<Integer> maxP=new PriorityQueue<>((x,y)->(y-x));
public void Insert(Integer num) {
if(minP.isEmpty()||num>minP.peek()){
minP.add(num);
}else{
maxP.add(num);
}
if(minP.size()==maxP.size()+2){
maxP.add(minP.poll());
}
if(maxP.size()==minP.size()+1){
minP.add(maxP.poll());
}
}
public Double GetMedian() {
if(minP.size()==maxP.size()){
return (double)(minP.peek()+maxP.peek())/2
}else{
return (double)minP.peek();
}
}
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((x,y)->(y-x));
priorityQueue.add(3);
priorityQueue.add(4);
System.out.println(priorityQueue.poll());
}
}