《网站建设与维护》讲义,简约大气展厅效果图,WordPress谷歌广告插件,mvc5网站开发之六 管理员数据流的中位数
原题#xff1a;力扣295.
设计一种数据结构可以支持添加整数和返回中位数的操作。
之前写过找中间用两个堆#xff0c;这道题就可以使用一个大顶堆和一个小顶堆。
大顶堆存储比较小的元素#xff0c;小顶堆存储比较大的元素。
class MedianFinder {Prio…数据流的中位数
原题力扣295.
设计一种数据结构可以支持添加整数和返回中位数的操作。
之前写过找中间用两个堆这道题就可以使用一个大顶堆和一个小顶堆。
大顶堆存储比较小的元素小顶堆存储比较大的元素。
class MedianFinder {PriorityQueueInteger minHeap;PriorityQueueInteger 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;}}
}如果对您有帮助请点赞关注支持我谢谢❤ 如有错误或者不足之处敬请指正❤ 个人主页星不易 ❤ 算法通关村专栏不易|算法通关村 ❤
