【Check 88】2024-05-31 - 295. 数据流的中位数

思路

两个堆（优先队列）把添加的数，分为较大部分存放在小顶堆max，和较小部分存放在大顶堆min

最终查询中数时，两堆大小不相同，则为奇数，取小顶堆堆顶元素，否则两堆堆顶之和除2

add时就需要不断维护，大的数放max，小的数放min add:O(logn)：堆的弹出和插入 find:O(1)

代码


class MedianFinder {
PriorityQueue<Integer> max;
PriorityQueue<Integer> min;
public MedianFinder() {
    //小顶堆，保存较大的数，小的先出堆
    max = new PriorityQueue<>();
    //大顶堆，保存较小的数，大的先出堆
    min = new PriorityQueue<>((o1,o2)->o2-o1);
}

public void addNum(int num) {
    //每次add，都会操作两个堆，保证max放较大的，min放较小的
    //第一次add时，数字经过操作最后放在max，所以奇数find时，max堆顶就是中位数
    if (max.size() != min.size()) {
        max.add(num);
        min.add(max.poll());
    } else {
        min.add(num);
        max.add(min.poll());
    }
}

public double findMedian() {
    return max.size() != min.size() ? max.peek() : (max.peek() + min.peek()) / 2.0;
}
}



### 复杂度
- 时间复杂度：O(logn)
- 空间复杂度：O(1)

larscheng / algo

【Check 88】2024-05-31 - 295. 数据流的中位数 #196

思路

代码