如何得到一個數(shù)據(jù)流中的中位數(shù)概龄？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值默终，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值汇歹。
思路：
分治思想：分為前后兩部分文搂，使用堆來維護
max和min 兩個堆
偶數(shù)情況：先加入min堆，調(diào)整之后秤朗，再poll出來煤蹭，加入max堆
奇數(shù)情況: 則是相反。
最后返回注意的是奇數(shù)的話取视，中位數(shù)在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());
}
}
}
