题解 | #数据流中的中位数#
数据流中的中位数
http://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1
import java.util.*;
queueMin.add(num);
}else{
queueMax.add(num);
queueMax.add(queueMin.poll());
}
while(queueMax.size()>queueMin.size()+1){
queueMin.add(queueMax.poll());
}
}
public Double GetMedian() {
if(queueMin.size()==queueMax.size()){
return (double)(queueMin.peek()+queueMax.peek())/2;
}else{
return queueMin.size()>queueMax.size()?(double)queueMin.peek():(double)queueMax.peek();
}
}
}
public class Solution {
//大顶堆存放小于等于中位数
PriorityQueue<Integer> queueMin = new PriorityQueue<>((x,y)->(y-x));
//小顶堆存放大等于中位数
PriorityQueue<Integer> queueMax = new PriorityQueue<>();
public void Insert(Integer num) {
//大顶堆为空直接放入
if(queueMin.size() == 0){
queueMin.add(num);
//值小于等于大顶堆堆顶，加入大顶堆，否则记入小顶堆
}else if(num <= queueMin.peek()){queueMin.add(num);
}else{
queueMax.add(num);
}
//维持大顶堆小顶堆容量相差最大为1
while(queueMin.size()>queueMax.size()+1){queueMax.add(queueMin.poll());
}
while(queueMax.size()>queueMin.size()+1){
queueMin.add(queueMax.poll());
}
}
public Double GetMedian() {
if(queueMin.size()==queueMax.size()){
return (double)(queueMin.peek()+queueMax.peek())/2;
}else{
return queueMin.size()>queueMax.size()?(double)queueMin.peek():(double)queueMax.peek();
}
}
}
其实能找到就很好了，当然收支能抵