[编程题]数据流中的中位数
数据流中的中位数
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());
}
}
}
查看11道真题和解析