🚩传送门：牛客题目
力扣题目

题目

如何得到一个数据流中的中位数？

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

数据范围：数据流中数个数满足 [NC]131. 数据流中的中位数 - 图1 ，大小满足 [NC]131. 数据流中的中位数 - 图2

进阶： 空间复杂度 [NC]131. 数据流中的中位数 - 图3 ， 时间复杂度 [NC]131. 数据流中的中位数 - 图4

示例1

输入：[5,2,3,4,1,6,7,0,8] 返回值：“5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 “ 说明：数据流里面不断吐出的是5,2,3…,则得到的平均数分别为5,(5+2)/2,3…

解题思路：优先队列 / 堆

建立一个 大顶堆[NC]131. 数据流中的中位数 - 图5 和 小顶堆[NC]131. 数据流中的中位数 - 图6 ，各保存列表的一半元素，且规定：

  • [NC]131. 数据流中的中位数 - 图7 保存 较小 的一半，长度为 [NC]131. 数据流中的中位数 - 图8（ [NC]131. 数据流中的中位数 - 图9 为偶数）或 [NC]131. 数据流中的中位数 - 图10（ [NC]131. 数据流中的中位数 - 图11 为奇数）
  • [NC]131. 数据流中的中位数 - 图12 保存 较大 的一半，长度为 [NC]131. 数据流中的中位数 - 图13（ [NC]131. 数据流中的中位数 - 图14 为偶数）或 [NC]131. 数据流中的中位数 - 图15（ [NC]131. 数据流中的中位数 - 图16 为奇数）

随后，中位数可仅根据[NC]131. 数据流中的中位数 - 图17 和[NC]131. 数据流中的中位数 - 图18 的堆顶元素计算得到。
image.png
添加算法流程：设总数 [NC]131. 数据流中的中位数 - 图20

  1. 当 [NC]131. 数据流中的中位数 - 图21（即 [NC]131. 数据流中的中位数 - 图22 为 偶数）：需向[NC]131. 数据流中的中位数 - 图23 添加一个元素。

    实现方法：将新元素 num 插入至 [NC]131. 数据流中的中位数 - 图24 ，再将 [NC]131. 数据流中的中位数 - 图25 堆顶元素插入至[NC]131. 数据流中的中位数 - 图26 ；

  2. 当 [NC]131. 数据流中的中位数 - 图27（即 [NC]131. 数据流中的中位数 - 图28 为 奇数）：需向[NC]131. 数据流中的中位数 - 图29 添加一个元素。

    实现方法：将新元素 num 插入至 [NC]131. 数据流中的中位数 - 图30 ，再将 [NC]131. 数据流中的中位数 - 图31 堆顶元素插入至[NC]131. 数据流中的中位数 - 图32 ；

查找算法流程：设总数 [NC]131. 数据流中的中位数 - 图33

  1. 当 [NC]131. 数据流中的中位数 - 图34（即 [NC]131. 数据流中的中位数 - 图35 为 偶数）：则中位数为 ([NC]131. 数据流中的中位数 - 图36的堆顶元素 + [NC]131. 数据流中的中位数 - 图37的堆顶元素 )/2。
  2. 当 [NC]131. 数据流中的中位数 - 图38（即 [NC]131. 数据流中的中位数 - 图39 为 奇数）：则中位数为[NC]131. 数据流中的中位数 - 图40的堆顶元素

复杂度分析

时间复杂度： [NC]131. 数据流中的中位数 - 图41 ，其中 [NC]131. 数据流中的中位数 - 图42 是数组长度。

  1.   - 查找中位数 ![](https://cdn.nlark.com/yuque/__latex/dc00d5b917657cffd78e71a4216106f0.svg#card=math&code=%5Csmall%20O%281%29&id=nSwcu)：获取堆顶元素使用 ![](https://cdn.nlark.com/yuque/__latex/dc00d5b917657cffd78e71a4216106f0.svg#card=math&code=%5Csmall%20O%281%29&id=IteMj)时间；
  2.   - 添加数字 ![](https://cdn.nlark.com/yuque/__latex/42433fa38a5bb64ddbf13bc74baefea6.svg#card=math&code=O%28%5Clog%20N%29&id=Aal9E) ： 堆的插入和弹出操作使用 ![](https://cdn.nlark.com/yuque/__latex/42433fa38a5bb64ddbf13bc74baefea6.svg#card=math&code=O%28%5Clog%20N%29&id=eL5eJ) 时间。

空间复杂度：[NC]131. 数据流中的中位数 - 图43 ： 其中[NC]131. 数据流中的中位数 - 图44为数据流中的元素数量

官方代码

  1. class MedianFinder {
  2.     Queue<Integer> A, B;
  3.     public MedianFinder() {
  4.         A = new PriorityQueue<>((o1, o2) -> {o2 - o1}); // 大顶堆，保存较小的一半
  5.         B = new PriorityQueue<>();                         // 小顶堆，保存较大的一半
  6.     }
  7.     public void addNum(int num) {
  8.         // 奇数，向B加
  9.         if(A.size() != B.size()) {
  10.             A.add(num);
  11.             B.add(A.poll());
  12.         } else { // 偶数,向A加
  13.             B.add(num);
  14.             A.add(B.poll());
  15.         }
  16.     }
  17.     public double findMedian() {
  18.         return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
  19.     }
  20. }

我的代码

  1. public class Solution {
  2.     // A 存数字小的区域的大根堆
  3.     PriorityQueue<Integer> ASmallMax=new PriorityQueue<>((o1,o2)->{
  4.         return o2-o1;
  5.     });
  6.     // B 存数字大的区域的小根堆
  7.     PriorityQueue<Integer> BBigMin=new PriorityQueue<>((o1,o2)->{
  8.         return o1-o2;
  9.     });
  11.     public void Insert(Integer num) {
  12.         // 奇数,向B中添加
  13.         if(ASmallMax.size()>BBigMin.size()){
  14.             ASmallMax.add(num);
  15.             BBigMin.add(ASmallMax.poll());
  16.         }else{ // 偶数,向A中添加
  17.             BBigMin.add(num);
  18.             ASmallMax.add(BBigMin.poll());
  19.         }
  20.         return ;
  21.     }
  23.     public Double GetMedian() {
  24.         // 奇数
  25.         if(ASmallMax.size()>BBigMin.size()){
  26.             return (double)ASmallMax.peek();
  27.         }
  28.         else{
  29.             return (ASmallMax.peek()+BBigMin.peek())/2.0;
  30.         }
  31.     }
  32. }