题目描述

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

解题思路

思路一：使用容器，排序
见代码：

import java.util.*;
// 运行时间：23ms
// 占用内存：9104k
public class Solution {
    ArrayList<Integer> res = new ArrayList<>();
    public void Insert(Integer num) {
        res.add(num);
        Collections.sort(res);/
        //或者把排序代码放在第二函数里面 能好些
    }

    public Double GetMedian() {
        int n = res.size();
        if (n % 2 == 0) {
            return Double.valueOf((res.get(n / 2) + res.get(n / 2 - 1)) / 2.0);
        } else {
            return Double.valueOf(res.get(n / 2));
        }
    }
}

思路二：使用最大最小堆
代码复杂：

  • 分析：对于海量数据和流的数据，用最大堆和最小堆来管理

  • 我们希望 数据分为[小]|[大]两个部分，细化一点
    [最大堆 | 左边最大 leftMax] [右边最小rightMin | 最小堆]

  • 定义一个规则：保证左边和右边个数相差不大于1，且左边小于右边

  • 1.数据是偶数的时候 insert的数据进入 [右边，最小堆]中

  • 1.1当插入的数字cur > leftMax时，直接插入到[右边，最小堆]中

  • 1.2当插入的数字cur < leftMax时，为了保证左边小于右边，

  • 先把cur插入[最大堆|左边最大leftMax]中，

  • 然后把leftMax放入[右边最小rightMin|最小堆]中

  • 就可以保证： 左边 < 右边

  • 2.数据是奇数的时候 insert的数据进入 [左边，最大堆]中

  • 2.1当插入的数字cur < rightMin时，直接插入到[左边，最小堆]中

  • 2.2当插入的数字cur > rightMin时，为了保证左边小于右边，

  • 先把cur插入[右边最小rightMin|最小堆]中，

  • 然后把rightMin放入[最大堆|左边最大leftMax]中

  • 就可以保证： 左边 < 右边

  • 最后：

  • 如果是偶数：中位数mid= (leftMax+right)/2

  • 如果是奇数：中位数mid= leftMax 因为先插入到左边，再插入到右边，为奇数时，中位数就是mid
    代码如下：

    //运行时间：15ms
//占用内存：9852k
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
  private PriorityQueue<Integer> min = new PriorityQueue<Integer>();
  //使用lambda表达式
  // private static PriorityQueue<Integer> maxHeap = new PriorityQueue<>((x, y) -> y - x);
  private PriorityQueue<Integer> max = new PriorityQueue<Integer>(15,new Comparator<Integer>() {
      public int compare(Integer o1, Integer o2) {
          return o2.compareTo(o1);
      }
  });
  private int count=0;
  public void Insert(Integer num) {
      count++;
      //让如果insert的数是奇数，则先插入到大顶堆中，然后取大顶堆堆顶插入到小顶堆中
      //始终保证小顶堆中的元素个数 大于等于 大顶堆中元素个数，即最多相差1
      if(count%2==1){
          max.offer(num);
          min.offer(max.poll());
      }else{
          min.offer(num);
          max.offer(min.poll());
      }
  }
  public Double GetMedian() {
      if(count%2 ==0)
          return (min.peek()+max.peek())/2.0;
      else return Double.valueOf(min.peek());
  }
}

    另一种代码

    //降序就是最大堆，lambda表达式了解下
  private static PriorityQueue<Integer> leftHeap = new PriorityQueue<>((x, y) -> y - x);
  //升序就是最小堆
  private static PriorityQueue<Integer> rightHeap = new PriorityQueue<>();
  //当前是奇数还是偶数
  private static boolean isOdd = true;
  public static void Insert(Integer num) {
      if(isOdd) {//数据是奇数的时候 insert的数据进入 [左边，最大堆]中
          if(leftHeap.isEmpty()) {
              leftHeap.add(num);
          }
          else {//这个时候rightHeap一定不是null，就不讨论了。考虑鲁棒性可以讨论
              int rightMin = rightHeap.peek();
              if(num <= rightMin) {//直接插入到[左边，最小堆]中
                  leftHeap.add(num);
              }else {
                  rightHeap.add(num);//先把cur插入[右边最小rightMin|最小堆]中
                  leftHeap.add(rightHeap.poll());//然后把rightMin放入[最大堆|左边最大leftMax]中
              }
          }
      }else {//数据是偶数的时候 insert的数据进入 [右边，最小堆]中
          //这个时候leftHeap一定不是null，就不讨论了。考虑鲁棒性可以讨论
              int leftMax = leftHeap.peek();
              if(num >= leftMax) {//直接插入到[右边，最小堆]中
                  rightHeap.add(num);
              }else {
                  leftHeap.add(num);//先把cur插入[右边最小rightMin|最小堆]中，
                  rightHeap.add(leftHeap.poll());//然后把rightMin放入[最大堆|左边最大leftMax]中
              }
      }
      isOdd = !isOdd;//改变奇偶性
  }

  public static Double GetMedian() {
      if(leftHeap.isEmpty()) return 0.0;
      if(!isOdd)//这里插入num改变了奇偶性，这里是奇数的意思
          return leftHeap.peek() / 1.0;
      else
          return (leftHeap.peek() + rightHeap.peek()) / 2.0;
  }

    参考博客

    https://sunweiguo.github.io/2019/03/18/%E5%89%91%E6%8C%87offer/%E3%80%90%E9%9D%A2%E8%AF%95%E9%A2%9863-%E6%95%B0%E6%8D%AE%E6%B5%81%E4%B8%AD%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0%E3%80%91/
    https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1?f=discussion