剑指offer 63.数据流中的中位数

剑指offer 63.数据流中的中位数

题目

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

思路

我一开始的想法，是排序之后直接找，但是复杂度有点高。
发现了一种新的方法，维持两个堆，一个最大堆，一个最小堆，确保最大堆的数都小于最小堆，两个堆的大小差距为1或0.
如果两边数量相同的话，取最大堆的最大值和最小堆的最小值和的一半即可，如果不同，那么就是多的那个。
java可以用优先队列，改一下比较器就可以了。

代码

int count = 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);


public void Insert(Integer num) {
  if (count % 2 == 0) {
    maxHeap.offer(num);
    int filteredMaxNum = maxHeap.poll();
    minHeap.offer(filteredMaxNum);
  } else {
    minHeap.offer(num);
    int filteredMinNum = minHeap.poll();
    maxHeap.offer(filteredMinNum);
  }
  count++;
}

public Double GetMedian() {
  if (count % 2 == 0) {
    return new Double((minHeap.peek() + maxHeap.peek())) / 2;
  } else {
    return new Double(minHeap.peek());
  }
}