数据流中的中位数

---

题目：

题解：

• 解题思路：

  • 
  • 

• 复杂度分析：

  • 时间复杂度：
    • 查找中位数 O(1) ： 获取堆顶元素使用 O(1) 时间；
    • 添加数字 O(logN) ： 堆的插入和弹出操作使用 O(logN) 时间。
  • 空间复杂度 O(N) ： 其中 N 为数据流中的元素数量，小顶堆 A 和大顶堆 B 最多同时保存 N 个元素。

• 代码：

  class MedianFinder {
      Queue<Integer> A,B;
      /** initialize your data structure here. */
      public MedianFinder() {
          A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
          B = new PriorityQueue<>((x,y) -> (y - x)); // 大顶堆，保存较小的一半
      }
  
      public void addNum(int num) {
          if (A.size() != B.size()) {
              A.add(num);
              B.add(A.poll());
          } else {
              B.add(num);
              A.add(B.poll());
          }
      }
  
      public double findMedian() {
          return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
      }
  }