LeetCode295. 数据流的中位数🌟🌟🌟🌟困难
课后作业
问题描述
原文链接：295. 数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
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
代码实现
Java
class MedianFinder {
//
Queue<Integer> max;// 保存较小那部分，并且多保存一个
Queue<Integer> min;// 保存较大那部分
public MedianFinder() {
max = new PriorityQueue<>((x,y)->(y - x));
min = new PriorityQueue<>();
}
public void addNum(int num) {
// 偶数
if(max.size() == min.size()){
min.offer(num);
max.offer(min.poll());
} else {
max.offer(num);
min.offer(max.poll());
}
}
public double findMedian() {
int size = max.size() + min.size();
if(size % 2 == 1){
return max.peek() * 1.0;
}else{
return (max.peek() + min.peek()) / 2.0;
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
Python
class MedianFinder(object):
def __init__(self):
self.max = [] # 保存较小那部分，并且多保存一个
self.min = [] # 保存较大那部分
def addNum(self, num):
# 偶数
if len(self.max) == len(self.min):
heapq.heappush(self.min, num)
heapq.heappush(self.max, -heapq.heappop(self.min))
else:
heapq.heappush(self.max, -num)
heapq.heappush(self.min, -heapq.heappop(self.max))
def findMedian(self):
size = len(self.max) + len(self.min)
if size % 2 == 1:
return float(-self.max[0])
else:
return (float(-self.max[0]) + float(self.min[0])) / 2
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
C++
class MedianFinder {
private:
priority_queue<int> max; // 保存较小那部分，并且多保存一个
priority_queue<int, vector<int>, greater<int>> min; // 保存较大那部分
public:
MedianFinder() {
}
void addNum(int num) {
// 偶数
if(max.size() == min.size()){
min.push(num);
max.push(min.top());
min.pop();
} else {
max.push(num);
min.push(max.top());
max.pop();
}
}
double findMedian() {
int size = max.size() + min.size();
if(size % 2 == 1){
return max.top() * 1.0;
}else{
return (max.top() + min.top()) / 2.0;
}
}
};
// Your MedianFinder object will be instantiated and called as such:
// MedianFinder* obj = new MedianFinder();
// obj->addNum(num);
// double param_2 = obj->findMedian();