中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
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：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 输入
["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
用两个堆实现
建立一个 小顶堆 A和 大顶堆 B，各保存列表的一半元素，且规定：
A保存较大的一半，B保存较小的一半
设元素总数为 N = m+n ，其中 m 和 n分别为 A 和 B 中的元素个数
addNum方法
当 m=n（即 N 为 偶数）：需向 A 添加一个元素。实现方法：将新元素 num 插入至 B，再将 B 堆顶元素插入至 A，这样能确保A的元素都比B大
当 m≠n（即 N 为 奇数）：需向 B 添加一个元素。实现方法：将新元素 num 插入至 A ，再将 A 堆顶元素插入至 B，这样能确保B的元素都比A小
findMedian方法
当 m=n（ N 为 偶数）：则中位数为 ( A 的堆顶元素 + B 的堆顶元素 ) / 2
当 m≠n（ N 为 奇数）：则中位数为 A 的堆顶元素
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
| class MedianFinder {
PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;
int size;
public MedianFinder() {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>((a,b) -> b - a);
size = 0;
}
public void addNum(int num) {
if(minHeap.size() == maxHeap.size()){
maxHeap.add(num);
minHeap.add(maxHeap.poll());
}else{
minHeap.add(num);
maxHeap.add(minHeap.poll());
}
}
public double findMedian() {
if(minHeap.size() == maxHeap.size()){
return (minHeap.peek() + maxHeap.peek()) / 2.0;
}else{
return minHeap.peek();
}
}
}
|