友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
295. 数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
-
例如
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
提示:
-
-105 <= num <= 105 -
在调用
findMedian之前，数据结构中至少有一个元素 -
最多
5 * 104次调用addNum和findMedian
思路分析
-
一刷
-
二刷
-
三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-08-29 20:43:20
*/
class MedianFinder {
Queue<Integer> topSmall;
Queue<Integer> topLarge;
public MedianFinder() {
// 小顶堆，顶部是最小的。保存较大的一半
topSmall = new PriorityQueue<>();
// 大顶堆，顶部是最大的。保存较小的一半
topLarge = new PriorityQueue<>((a, b) -> b - a);
}
public void addNum(int num) {
if (topSmall.size() != topLarge.size()) {
// 倒腾一下，实际 topLarge 中的元素增加了
topSmall.add(num);
topLarge.add(topSmall.poll());
} else {
// 倒腾一下，实际 topSmall 中的元素增加了
topLarge.add(num);
topSmall.add(topLarge.poll());
}
}
public double findMedian() {
return topSmall.size() != topLarge.size() ?
topSmall.peek() : (topSmall.peek() + topLarge.peek()) / 2.0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-19 16:37:23
*/
class MedianFinder {
Queue<Integer> topSmall;
Queue<Integer> topLarge;
public MedianFinder() {
// 小顶堆，顶部是最小的。保存较大的一半
topSmall = new PriorityQueue<>();
// 大顶堆，顶部是最大的。保存较小的一半
topLarge = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
}
public void addNum(int num) {
if (topSmall.size() != topLarge.size()) {
topSmall.offer(num);
topLarge.offer(topSmall.poll());
} else {
topLarge.offer(num);
topSmall.offer(topLarge.poll());
}
}
public double findMedian() {
return topSmall.size() == topLarge.size() ?
(topSmall.peek() + topLarge.peek()) / 2.0 : topSmall.peek();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-03-28 18:53:57
*/
class MedianFinder {
// 小顶堆，顶部是最小的。保存较大的一半
PriorityQueue<Integer> topSmall;
// 大顶堆，顶部是最大的。保存较小的一半
PriorityQueue<Integer> topLarge;
public MedianFinder() {
topSmall = new PriorityQueue<>();
// 注意：这里的 Comparator 是反向，不能直接用 Integer::compare 代替
topLarge = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
}
public void addNum(int num) {
if (topSmall.size() == topLarge.size()) {
topLarge.offer(num);
topSmall.offer(topLarge.poll());
} else {
topSmall.offer(num);
topLarge.offer(topSmall.poll());
}
}
public double findMedian() {
return topSmall.size() == topLarge.size()
? (topSmall.peek() + topLarge.peek()) / 2.0 : topSmall.peek();
}
}