力扣295. 数据流的中位数
class MedianFinder {
/* Maintain a large top heap and a small top heap */
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
public MedianFinder() {
}
/**
* Data flow inserts data
*
* @param num Data to be inserted
*/
public void addNum(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
/**
Maintain the number relationship between two heaps
1. The number of elements in the large top heap is not less than that in the small top heap
2. The number of small top heap elements can be less than the number of large top heap elements minus 1
*/
while (maxHeap.size() < minHeap.size()) {
Integer temp = minHeap.poll();
maxHeap.add(temp);
}
while (minHeap.size() < maxHeap.size() - 1) {
Integer temp = maxHeap.poll();
minHeap.add(temp);
}
}
/**
* Find the median
*
* @return double
*/
public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (minHeap.peek() + maxHeap.peek()) / 2f;
} else {
return maxHeap.peek();
}
}
}