2015做那个网站致富今天的国际新闻

数据流的中位数

原题：力扣295.

设计一种数据结构可以支持添加整数和返回中位数的操作。

之前写过找中间用两个堆，这道题就可以使用一个大顶堆和一个小顶堆。

大顶堆存储比较小的元素，小顶堆存储比较大的元素。

class MedianFinder {PriorityQueue<Integer> minHeap;PriorityQueue<Integer> maxHeap;public MedianFinder() {this.minHeap = new PriorityQueue<>();this.maxHeap = new PriorityQueue<>((a, b) -> b - a);}public void addNum(int num) {if (minHeap.isEmpty() || num > minHeap.peek()) {// 进入小顶堆minHeap.offer(num);// 平衡两个堆的长度if (minHeap.size() - maxHeap.size() > 1) {maxHeap.offer(minHeap.poll());}} else {// 进入大顶堆maxHeap.offer(num);// 平衡两个堆的长度if (maxHeap.size() - minHeap.size() > 0) {minHeap.offer(maxHeap.poll());}}}public double findMedian() {if (minHeap.size() > maxHeap.size()) {return minHeap.peek();} else {return ((minHeap.peek() + maxHeap.peek()) / 2.0;}}
}

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤
个人主页：星不易 ❤
算法通关村专栏：不易|算法通关村 ❤