帮公司做网站运营,南京 网站制作公司哪家好,百度收录网站有什么好处,学做网站是什么数据流的中位数
原题#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;}}
}如果对您有帮助请点赞关注支持我谢谢❤ 如有错误或者不足之处敬请指正❤ 个人主页星不易 ❤ 算法通关村专栏不易|算法通关村 ❤
