[编程题]数据流中的中位数
数据流中的中位数
http://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1
import java.util.PriorityQueue; import java.util.Comparator; public class Solution { //小顶堆,从小到大排列 private PriorityQueue<Integer> min=new PriorityQueue<Integer>(); //大顶堆,从大到小的排列 private PriorityQueue<Integer> max=new PriorityQueue<Integer>(15,new Comparator<Integer>(){ @Override public int compare(Integer o1,Integer o2){ return o2-o1; } }); //如果当前的数据个数为0 int count=0; public void Insert(Integer num) { if(count%2==0){ max.offer(num); Integer curNum=max.poll(); min.offer(curNum); }else{ //如果为奇数 min.offer(num); Integer curNum=min.poll(); max.offer(curNum); } //插入一个数据后加1 count++; } public Double GetMedian() { //如果输入流的数据个数为奇数 if(count%2==0){ return new Double(min.peek()+max.peek())/2; }else{ return new Double(min.peek()); } } }