剑指offer63.数据流中的中位数题目如何得到一个数据流中的中位数？

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

题目

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

思路

我一开始的想法，是排序之后直接找，但是复杂度有点高。

发现了一种新的方法，维持两个堆，一个最大堆，一个最小堆，确保最大堆的数都小于最小堆，两个堆的大小差距为1或0.

如果两边数量相同的话，取最大堆的最大值和最小堆的最小值和的一半即可，如果不同，那么就是多的那个。

java可以用优先队列，改一下比较器就可以了。

代码


int count = 0;
PriorityQueue minHeap = new PriorityQueue<>();
PriorityQueue 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());
}
}