算法题:数据流中的中位数
2017-02-19 本文已影响0人
万事屋FIN
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
思路:
分治思想:分为前后两部分,使用堆来维护
max和min 两个堆
偶数情况:先加入min堆,调整之后,再poll出来,加入max堆
奇数情况: 则是相反。
最后返回注意的是奇数的话,中位数在min堆中
详情可以画图注意
import java.util.*;
public class Solution {
private PriorityQueue<Integer> min=new PriorityQueue<>();
private PriorityQueue<Integer> max=new PriorityQueue<>(11, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
private int count=0;
public void Insert(Integer num) {
if(count%2==0){
max.offer(num);
min.offer(max.poll());
}else{
min.offer(num);
max.offer(min.poll());
}
count++;
}
public Double GetMedian() {
if(count%2==0){
return new Double((min.peek()+max.peek()))/2;
}else{
return new Double (min.peek());
}
}
}