数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
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我们用两个优先队列
\textit{queMax}
和
\textit{queMin}
分别记录大于中位数的数和小于等于中位数的数。当累计添加的数的数量为奇数时，
\textit{queMin}
中的数的数量比
\textit{queMax}
多一个，此时中位数为
\textit{queMin}
的队头。当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。
当我们尝试添加一个数
\textit{num}
到数据结构中，我们需要分情况讨论：
\textit{num} \leq \max \{\textit{queMin}\}
此时
\textit{num}
小于等于中位数，我们需要将该数添加到
\textit{queMin}
中。新的中位数将小于等于原来的中位数，因此我们可能需要将
\textit{queMin}
中最大的数移动到
\textit{queMax}
中。
textit{num} > \max \{\textit{queMin}\}
此时
\textit{num}
大于中位数，我们需要将该数添加到
\textit{queMin}
中。新的中位数将大于等于原来的中位数，因此我们可能需要将
\textit{queMax}
中最小的数移动到
\textit{queMin}
中。
特别地，当累计添加的数的数量为
0
时，我们将
\textit{num}
添加到
\textit{queMin}
中。
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> queMin;
priority_queue<int, vector<int>, greater<int>> queMax;
MedianFinder() {}
void addNum(int num) {
if (queMin.empty() || num <= queMin.top()) {
queMin.push(num);
if (queMax.size() + 1 < queMin.size()) {
queMax.push(queMin.top());
queMin.pop();
}
} else {
queMax.push(num);
if (queMax.size() > queMin.size()) {
queMin.push(queMax.top());
queMax.pop();
}
}
}
double findMedian() {
if (queMin.size() > queMax.size()) {
return queMin.top();
}
return (queMin.top() + queMax.top()) / 2.0;
}
};复杂度分析
时间复杂度：
\textit{addNum}
:
O(\log n)
，其中
n
为累计添加的数的数量。
\textit{findMedian}:
O(1)
。
空间复杂度：
O(n)
，主要为优先队列的开销。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-12-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读