剑指 Offer 41. 数据流中的中位数 (opens new window)

1.二分+列表

分析：用list结合维护一个有序列表。每次插入新的元素时，二分查找找到list集合的插入位置。

class MedianFinder {
    List<Integer> list;
    /** initialize your data structure here. */
    public MedianFinder() {
        list =new ArrayList<>();
    }
    public void addNum(int num) {
        int left=0,right=list.size()-1;
        while(left<right){
            int mid=(left+right)/2;
            if(list.get(mid)>=num) right=mid;
            else left=mid+1;
        }
        if(list.size()!=0&&list.get(left)<num) list.add(left+1,num);
        else list.add(left,num);
    }
    public double findMedian() {
        if(list.size()%2==1) return (double)list.get(list.size()/2);
        double a=(double)list.get(list.size()/2-1),b=(double)list.get(list.size()/2);
        return (a+b)/2;
    }
}