题目链接

LeetCode
牛客网

题目描述

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

进阶:

  1. 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
  2. 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

    解题思路

    方法一：大顶堆和小顶堆

    用一个大顶堆存小于等于中位数的一半值
    用一个小顶堆存大于等于中位数的一半值
  1. class MedianFinder {
  2.     PriorityQueue<Integer> minHeap, maxHeap;
  3.     public MedianFinder() {
  4.         // 小顶堆 堆顶是最小值   小顶堆里放的都是大于中位数的值
  5.         minHeap = new PriorityQueue<Integer>(); 
  6.         // 大顶堆 堆顶是最大值   大顶堆里放的都是小于等于中位数的值
  7.         maxHeap = new PriorityQueue<Integer>((a, b) -> b - a);
  8.     }
  10.     public void addNum(int num) {
  11.         minHeap.offer(num);
  12.         // 大顶堆中的值的个数大于等于小顶堆
  13.         if(maxHeap.size() < minHeap.size()){
  14.             maxHeap.offer(minHeap.poll());
  15.         }
  16.         // 如果小顶堆的最小值小于大顶堆的最大值，将两个值换位置
  17.         if(!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()){
  18.             minHeap.offer(maxHeap.poll());
  19.             maxHeap.offer(minHeap.poll());
  20.         }
  21.     }
  22.     public double findMedian() {
  23.         if(maxHeap.size() == minHeap.size()){
  24.             return (double)(maxHeap.peek() + minHeap.peek())/2.0;
  25.         }
  26.         return (double)maxHeap.peek();
  27.     }
  28. }
  30. /**
  31.  * Your MedianFinder object will be instantiated and called as such:
  32.  * MedianFinder obj = new MedianFinder();
  33.  * obj.addNum(num);
  34.  * double param_2 = obj.findMedian();
  35.  */
  1. class MedianFinder {
  2.     PriorityQueue<Integer> minHeap, maxHeap;
  3.     public MedianFinder() {
  4.         minHeap = new PriorityQueue<Integer>();
  5.         maxHeap = new PriorityQueue<Integer>((a, b) -> b - a);
  6.     }
  8.     public void addNum(int num) {
  9.         // 下面代码保证 minHeap 中的最小值大于 maxHeap 中的最大值
  10.         minHeap.offer(num);
  11.         // minHeap中最小的给maxHeap
  12.         maxHeap.offer(minHeap.poll());
  13.         // maxHeap中最大的给minHeap
  14.         if(minHeap.size() < maxHeap.size()){
  15.             minHeap.offer(maxHeap.poll());
  16.         }
  17.     }
  19.     public double findMedian() {
  20.         if(minHeap.size() > maxHeap.size()){
  21.             return (double)minHeap.peek();
  22.         }
  23.         return ((double)minHeap.peek() + (double)maxHeap.peek()) / 2.0;
  24.     }
  25. }
  27. /**
  28.  * Your MedianFinder object will be instantiated and called as such:
  29.  * MedianFinder obj = new MedianFinder();
  30.  * obj.addNum(num);
  31.  * double param_2 = obj.findMedian();
  32.  */
  • 时间复杂度 findMedian() O(1) addNum() O(log n)
  • 空间复杂度 O(n)