大家好，我就是那个在B站讲算法的「华南溜达虎」。
最近美团的秋招offer开始陆续发放了，看网上有同学表示不太满意，嫌给的太少了，觉得有点羞辱人。我赶紧去搜了一下美团校招的薪资，才发现后端和测开白菜价达到了23k左右，算法白菜价达到了25k左右，平均比去年白菜价多了2k，感觉这也不低啊。
看了评论区才发现，这价格在大部分人眼里确实不低了，很多人表示楼主觉得低可以选择不接，又不缺你一个。不过也不排除楼主能力很强，预期能拿sp却给了个白菜价有点失落，毕竟才是第一个开奖的offer，可以再等等后面的。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「数据流的中位数」。
题目描述
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 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 以内的答案将被接受。
举个例子：
输入
["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
思路解析
维护一个大根堆m_small和一个小根堆m_large，在插入元素的过程中始终保持大根堆m_small的最大值 小于 小根堆m_large的最小值，且保持两个堆之间的元素个数相差不超过1，即｜m_small.size() - m_large.size()｜ <= 1。
数据流的中位数存在三种情况：
m_small.size() > m_large.size()，中位数为m_small.top()。m_large.size() > m_small.size()，中位数为m_large.top()。m_small.size() == m_large.size()，中位数为(m_small.top() + m_large.top()) / 2.0。
比如，arr = [1, 2, 3, 4]对应的大根堆和小根堆情况如下图。
其中位数为(2 + 3) / 2.0 = 2.5。
下面我们给出c++和python的两种代码实现。
C++代码
class MedianFinder {
public:
MedianFinder() {
}
void addNum(int num) {
//元素先插到大根堆
m_small.push(num);
//保证大根堆m_small的最大值 小于 小根堆m_large的最小值
if (m_small.size() && m_large.size() && m_small.top() > m_large.top()) {
m_large.push(m_small.top());
m_small.pop();
}
//保持两个堆之间元素个数相差不超过1
if (m_small.size() > m_large.size() + 1) {
m_large.push(m_small.top());
m_small.pop();
}
//保持两个堆之间元素个数相差不超过1
if (m_large.size() > m_small.size() + 1) {
m_small.push(m_large.top());
m_large.pop();
}
}
double findMedian() {
if (m_large.size() > m_small.size()) {
return m_large.top();
}
if (m_small.size() > m_large.size()) {
return m_small.top();
}
return (m_large.top() + m_small.top()) / 2.0;
}
private:
//大根堆
priority_queue<int, vector<int>, less<int>> m_small;
//小根堆
priority_queue<int, vector<int>, greater<int>> m_large;
};
python代码
class MedianFinder(object):
def __init__(self):
# 大根堆，存储较小的一半
self.small = []
# 小根堆，存储较大的一半
self.large = []
def addNum(self, num):
"""
:type num: int
:rtype: None
"""
# 元素先插到大根堆
heapq.heappush(self.small, -num)
# 保证大根堆 self.small 的最大值小于小根堆 self.large 的最小值
if self.small and self.large and -self.small[0] > self.large[0]:
heapq.heappush(self.large, -heapq.heappop(self.small))
# 保持两个堆之间元素个数相差不超过1
if len(self.small) > len(self.large) + 1:
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small) + 1:
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self):
"""
:rtype: float
"""
if len(self.large) > len(self.small):
return float(self.large[0])
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2.0
复杂度分析
时间复杂度： 优先队列中插入元素的时间复杂度为O(logk)，其中k为优先队列对应堆的高度。查找中位数的时间复杂度为O(1)，即取堆顶元素的开销。
空间复杂度： O(n)，n为优先队列中节点的个数。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
