本文共 1495 字，大约阅读时间需要 4 分钟。

题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。

示例 1：

输入： [“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”] [[],[1],[2],[],[3],[]] 输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入： [“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”] [[],[2],[],[3],[]] 输出：[null,null,2.00000,null,2.50000]

限制：

最多会对 addNum、findMedian 进行 50000 次调用。

答案

/*** 用大小堆* 如果数组长度为奇数，中位数是最中间的那个，如果长度为偶数是中间偏左的那个元素* 使用最大堆来存储等于或小于中位数的值，只需poll一次就可弹出当前的中位数，使用最小堆来存储大于中位数的值。* 此外需要保持两个堆平衡，因为我们要获得中位数，所以最大堆的大小将始终等于或比最小堆的大小大1,保持平衡就好*/class MedianFinder {
       private PriorityQueue
   
     minP, maxP;    public MedianFinder(){
           minP = new PriorityQueue<>();        maxP = new PriorityQueue(Collections.reverseOrder());    }    public void addNum(int num){
           if(minP.size() != maxP.size()){
               minP.add(num);//这个数不一定是较小的一般，所以先加入小顶堆            maxP.add(minP.poll());//再往大顶堆中加入小顶堆出堆的元素        }else{
               maxP.add(num);            minP.add(maxP.poll());        }    }    public double findMedian(){
           return minP.size() != maxP.size()? minP.peek():(minP.peek() + maxP.peek()) / 2.0;    }}/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */
   

转载地址：https://darkness.blog.csdn.net/article/details/115219746 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！