hot100：76数据流的中位数

题目链接：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

算法思想：

这题的题意说明简单，就是求一组数据的中位数，如果是奇数个数据最中间的数据就是中位数，如果是偶数个数据最中间两个数的平均数就是中位数；这题的做法有很多：

解法一：每次add的时候进行sort，时间复杂度是O(nlogn)

解法二：插入排序的思想,时间复杂度是O(n)

解法三：用大小堆的思想，时间复杂度是O(logn)

解法一和解法二针对这题会超时，以后找中位数就使用大小堆的思想就可以了

分别定义两个堆left、right，left表示的是一组数据的左半部分，长度为m，right表示的是一组数据的右半部分，长度为n，有两种情况m=n或者m=n+1；所以在add元素的时候也要分情况讨论：第一种情况m=n，第二种情况是m=n+1，这样就会导致在添加元素的时候出现m=n+2，要进行处理

//大小堆来维护数据流的中位数
class MedianFinder {
    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    public MedianFinder() {
        left = new PriorityQueue<Integer>((a, b) -> b - a);//大根堆
        right = new PriorityQueue<Integer>((a, b) -> a - b);//小根堆
    }
    
    public void addNum(int num) {
        //分情况讨论
        //m表示大根堆元素个数 n表示小根堆元素个数
        //所以有两种情况 m=n 或者 m=n+1
        if(left.size() == right.size()) {
            //left为空或者添加的元素小于大根堆的最大元素
            if(left.isEmpty() || num <= left.peek()) {
                left.offer(num);
            } else {
                //添加到小根堆之后小根堆的长度比大根堆大1 所以需要将小根堆的根顶元素加入到大根堆中
                right.offer(num);
                left.offer(right.poll());
            }
        } else {
            if(num <= left.peek()) {
                right.offer(left.poll());
                left.offer(num);
            } else {
                right.offer(num);
            }
        }
    }
    
    public double findMedian() {
        if(left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        }
        return left.peek();
    }
}