友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
295. Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. For example,
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
-
void addNum(int num) - Add a integer number from the data stream to the data structure.
-
double findMedian() - Return the median of all elements so far.
Example:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2Follow up:
-
If all integer numbers from the stream are between 0 and 100, how would you optimize it?
-
If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?
思路分析
-
一刷
-
二刷
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();
}
}