295. 数据流的中位数

能把在面前行走的机会抓住的人，十有八九都会成功。

参考295. 数据流的中位数。

题目

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。

• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。

• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释 MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

解题思路

• 排序：由于Java没有有序队列,可以考虑在需要获取中位数的时候进行排序。
• 优先队列：优先队列无法随机读取也不保证里面的元素有序,但是可以维护两个优先队列,一个头维护最大的,一个头维护最小的,添加时保证两个队列长度差不超过1,则中位数由两个头的值获取。

排序

class MedianFinder {

    //Collections.sort(list); //使用ArrayList超时 Java没有SortedList
    int[] list = new int[50000];
    int n = 0;

    public MedianFinder() {
    }
    
    public void addNum(int num) {
        list[n++] = num;
    }
    
    public double findMedian() {
        Arrays.sort(list,0,n);
        return n%2 == 0? (list[(n-1)/2]+list[n/2])/2.0:list[n/2];
    }
}

复杂度分析

• 时间复杂度：O(k*nlogn)，排序耗时nlogn,k为调用findMedian次数。
• 空间复杂度：O(n)，n为数组使用空间。

优先队列

class MedianFinder {

    //维护两个优先队列 保证两者长度差不超过1  treeMap不能存重复元素
    PriorityQueue<Integer> pq1,pq2;

    public MedianFinder() {
        pq1 = new PriorityQueue<>((a,b)->b-a);//存储一半的数 比较小 3 2 1
        pq2 = new PriorityQueue<>();//存储另一半的数 比较大 4 5 6
    }
    
    public void addNum(int num) {
        if(pq1.size() == 0 && pq2.size() == 0) {
            pq1.add(num);
        }
        else {
            if(pq2.size() <= pq1.size()) {
                if(num >= pq1.peek()) pq2.add(num);
                else {
                    pq2.add(pq1.poll());
                    pq1.add(num);
                }
            }else {
                if(num >= pq2.peek()){
                    pq1.add(pq2.poll());
                    pq2.add(num);
                } 
                else {
                    pq1.add(num);
                }
            }
        }
    }
    
    public double findMedian() {
        if(pq1.size() == pq2.size()) {
            return (pq1.peek() + pq2.peek())/2.0;
        }else {
            if(pq1.size() > pq2.size()) return pq1.peek();
            else return pq2.peek();
        }
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，优先队列添加操作的时间复杂度为logn,总共有n次添加操作。
• 空间复杂度：O(n)，n为优先队列使用空间。