[LeetCode Hot 100] LeetCode295. 数据流的中位数
发布时间 2023-12-08 17:08:34作者: Ac_c0mpany丶
题目描述
思路:一个大根堆+一个小根堆+保持数量
- 一个大根堆用来记录数轴左边的数值
- 一个小根堆用来记录数轴右边的数值
- 大根堆的容量要么等于小根堆的容量(此时是偶数个有序整数列表),要么大根堆的容量比小根堆的容量大1(此时是奇数个有序整数列表)
- 如果数量不符合上述条件,则将超过容量的那个堆的堆顶元素插入到另一个堆中
- 求中位数
- 如果是偶数个容量:则分别取两个堆的堆顶元素,再除以2.0。
- 如果是奇数个容量:则去大顶堆的堆顶元素即可。
方法一:
class MedianFinder {
// 大根堆
PriorityQueue<Integer> heap_down = new PriorityQueue<>((e1, e2) -> e2 - e1);
// 小根堆
PriorityQueue<Integer> heap_up = new PriorityQueue<>();
public MedianFinder() {
}
public void addNum(int num) {
if (heap_down.isEmpty() || num < heap_down.peek()) {
heap_down.add(num);
if (heap_down.size() > heap_up.size() + 1) {
heap_up.add(heap_down.remove());
}
} else {
heap_up.add(num);
if (heap_up.size() > heap_down.size()) {
heap_down.add(heap_up.remove());
}
}
}
public double findMedian() {
int size = heap_down.size() + heap_up.size();
if (size % 2 == 0) {
return (heap_down.peek() + heap_up.peek()) / 2.0;
} else {
return heap_down.peek();
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/