数据流中的中位数

Posted on In Views: Waline: Views: Symbols count in article: 714 Reading time ≈ 1 mins.

题解方法

  • 优先队列

优先队列

使用两个优先队列 $maxQueue$ 和 $minQueue$ 分别记录大于中位数的数和小于等于中位数的数。

当累计添加的数的数量为奇数时，$minQueue$ 中的数比 $maxQueue$ 多一个，此时中位数为 $minQueue$ 的队头；当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。

核心代码

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void addNum(int num) {
	if (minQueue.isEmpty() || num <= minQueue.peek()) {
		minQueue.offer(num);
		if (minQueue.size() > maxQueue.size() + 1) {
			maxQueue.offer(minQueue.poll());
		}
	} else {
		maxQueue.offer(num);
		if (maxQueue.size() > minQueue.size()) {
			minQueue.offer(maxQueue.poll());
		}
	}
}

public double findMedian() {
	if (minQueue.size() > maxQueue.size()) {
		return minQueue.element();
	}
	return (minQueue.element() + maxQueue.element()) / 2.0;
}

题目来源

数据流中的中位数 - 力扣（LeetCode）