目录
1. 题目列表
题目列表:
序号 | 题目 | 难度 |
---|---|---|
1 | 295. 数据流的中位数 | 困难 |
2. 应用
2.1. Leetcode 295. 数据流的中位数
2.1.1. 题目
中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。
- 例如 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
2.1.2. 解题思路
我们可以考虑维护两个优先队列:
-
small
:维护一个大根堆用于保存较小的元素,其中,堆顶的元素最大; -
large
:维护一个小根堆用于保存较大的元素,其中,堆顶的元素最小。
假设添加的元素个数为 \(n\),如果 \(n\) 为奇数,我们保持 \(small\) 和 \(large\) 中的元素个数分别为 \(\frac{n}{2} + 1\)、\(\frac{n}{2}\),这样,\(small\) 中多的元素,就是中位数。
如果 \(n\) 为偶数,那么,中位数就是两个堆的堆顶元素的平均值。
当我们尝试添加一个元素 \(num\) 的时候,如果其中一个堆中的元素较多,可以将元素 \(num\) 放入该堆,然后再将堆顶的元素,放入另一个堆中。
2.1.3. 代码实现
class MedianFinder {
private PriorityQueue<Integer> small; // 大根堆,保存较小的元素
private PriorityQueue<Integer> large; // 小根堆,保存较大的元素
public MedianFinder() {
small = new PriorityQueue<>((a, b) -> a - b);
large = new PriorityQueue<>((a, b) -> b - a);
}
public void addNum(int num) {
if (small.size() >= large.size()) {
small.offer(num);
large.offer(small.poll());
} else {
large.offer(num);
small.offer(large.poll());
}
}
public double findMedian() {
if (large.size() < small.size()) {
return small.peek();
} else if (large.size() > small.size()) {
return large.peek();
} else {
return (small.peek() + large.peek()) / 2.0;
}
}
}
参考:
标签:优先级,队列,元素,中位数,large,应用,small,2.1,MedianFinder From: https://www.cnblogs.com/larry1024/p/17994557