高中制作网站怎么做,网站维护 内容,望野古诗王绩,中国风电商网站建设一、题目要求
中位数是有序整数列表中的中间值。如果列表的大小是偶数#xff0c;则没有中间值#xff0c;中位数是两个中间值的平均值。 例如 arr [2,3,4] 的中位数是 3 。 例如 arr [2,3] 的中位数是 (2 3) / 2 2.5 。
实现 MedianFinder 类: MedianFinder() 初始化 …一、题目要求
中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。 例如 arr [2,3,4] 的中位数是 3 。 例如 arr [2,3] 的中位数是 (2 3) / 2 2.5 。
实现 MedianFinder 类: MedianFinder() 初始化 MedianFinder 对象。 void addNum(int num) 将数据流中的整数 num 添加到数据结构中。 double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
示例 1 输入 [“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0]
解释 MedianFinder medianFinder new MedianFinder(); medianFinder.addNum(1); // arr [1] medianFinder.addNum(2); // arr [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0 提示:
-105 num 105 在调用 findMedian 之前数据结构中至少有一个元素 最多 5 * 104 次调用 addNum 和 findMedian
二、实现代码
原理使用了两个堆存储数据一个最大堆用于存储较小的一半元素另一个最小堆用于存储较大的一半元素然后根据堆顶元素计算得到中位数。 1. Java
class MedianFinder {private PriorityQueueInteger low;private PriorityQueueInteger high;public MedianFinder() {// Max-heap to store the smaller half elementslow new PriorityQueue((a, b) - b - a);// Min-heap to store the larger half elementshigh new PriorityQueue();}public void addNum(int num) {low.offer(num);high.offer(low.poll());if (low.size() high.size()) {low.offer(high.poll());}}public double findMedian() {if (low.size() high.size()) {return low.peek();} else {return (low.peek() high.peek()) / 2.0;}}
}2. C
class MedianFinder {
private:priority_queueint low; // Max-heappriority_queueint, vectorint, greaterint high; // Min-heappublic:MedianFinder() { }void addNum(int num) {low.push(num);high.push(low.top());low.pop();if (low.size() high.size()) {low.push(high.top());high.pop();}}double findMedian() {if (low.size() high.size()) {return low.top();} else {return (low.top() high.top()) / 2.0;}}
};3. Python3
class MedianFinder:def __init__(self):self.low [] # max-heap (inverted min-heap)self.high [] # min-heapdef addNum(self, num: int) - None:heapq.heappush(self.low, -num)heapq.heappush(self.high, -heapq.heappop(self.low))if len(self.low) len(self.high):heapq.heappush(self.low, -heapq.heappop(self.high))def findMedian(self) - float:if len(self.low) len(self.high):return -self.low[0]else:return (-self.low[0] self.high[0]) / 2.0注如果四python会出错只能是python3
