#P4083. 数据流的中位数
-
ID: 2324
Tried: 31
Accepted: 9
Difficulty: 6
数据流的中位数
题目内容
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如 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以内的答案将被接受。
输入描述
- 第一行输入一个整数 q，表示操作次数。
- 接下来 q 行，每行是一个操作：
- 若为 "add x"，表示添加一个数字 x；
- 若为 "median"，表示查询当前所有数字的中位数。
输出描述
对于每个 "median" 操作，输出一行中位数，保留 1 位小数。
样例1
输入
5
add 1
add 2
median
add 3
median
输出
1.5
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
数据流的中位数
题解思路
方法：双堆法（大顶堆 + 小顶堆）
为了高效地求解中位数，我们可以使用两个堆维护数据流的左右两半部分：
- 最大堆（left，存较小的一半）：堆顶是左半边最大值；
- 最小堆（right，存较大的一半）：堆顶是右半边最小值；
平衡策略：
- 添加元素时，先放入最大堆，再将最大堆堆顶移动到最小堆；
- 如果最小堆元素比最大堆多，则从最小堆弹出一个最小元素到最大堆，确保平衡。
查找中位数：
- 若总数是奇数，中位数为最大堆堆顶；
- 若总数是偶数，中位数为两个堆顶平均值。
复杂度分析
addNum时间复杂度：O(logn)（堆操作）findMedian时间复杂度：O(1)- 空间复杂度：O(n)
Python 实现
import sys
import heapq
class MedianFinder:
def __init__(self):
self.left = [] # 最大堆（存负数）
self.right = [] # 最小堆
def addNum(self, num):
heapq.heappush(self.left, -num) # 先放到最大堆
heapq.heappush(self.right, -heapq.heappop(self.left)) # 保证最小堆最小
if len(self.right) > len(self.left): # 平衡两个堆
heapq.heappush(self.left, -heapq.heappop(self.right))
def findMedian(self):
if len(self.left) > len(self.right):
return -self.left[0]
else:
return (-self.left[0] + self.right[0]) / 2
# 主程序（ACM风格）
mf = MedianFinder()
q = int(sys.stdin.readline().strip())
for _ in range(q):
parts = sys.stdin.readline().strip().split()
if parts[0] == 'add':
mf.addNum(int(parts[1]))
elif parts[0] == 'median':
print(f"{mf.findMedian():.1f}")
C++ 实现
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
class MedianFinder {
priority_queue<int> left; // 大顶堆
priority_queue<int, vector<int>, greater<int>> right; // 小顶堆
public:
void addNum(int num) {
left.push(num);
right.push(left.top());
left.pop();
if (right.size() > left.size()) {
left.push(right.top());
right.pop();
}
}
double findMedian() {
if (left.size() > right.size()) return left.top();
return (left.top() + right.top()) / 2.0;
}
};
int main() {
int q;
cin >> q;
MedianFinder mf;
while (q--) {
string op;
cin >> op;
if (op == "add") {
int x;
cin >> x;
mf.addNum(x);
} else if (op == "median") {
cout << fixed << setprecision(1) << mf.findMedian() << endl;
}
}
return 0;
}
Java 实现
import java.util.*;
public class Main {
static class MedianFinder {
PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> right = new PriorityQueue<>();
public void addNum(int num) {
left.offer(num);
right.offer(left.poll());
if (right.size() > left.size()) {
left.offer(right.poll());
}
}
public double findMedian() {
if (left.size() > right.size()) return left.peek();
return (left.peek() + right.peek()) / 2.0;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
MedianFinder mf = new MedianFinder();
while (q-- > 0) {
String cmd = sc.next();
if (cmd.equals("add")) {
int x = sc.nextInt();
mf.addNum(x);
} else if (cmd.equals("median")) {
System.out.printf("%.1f\n", mf.findMedian());
}
}
}
}