mirror of https://github.com/doocs/leetcode.git
27 lines
716 B
Java
27 lines
716 B
Java
class MedianFinder {
|
|
private PriorityQueue<Integer> minQ = new PriorityQueue<>();
|
|
private PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
|
|
|
|
public MedianFinder() {
|
|
}
|
|
|
|
public void addNum(int num) {
|
|
maxQ.offer(num);
|
|
minQ.offer(maxQ.poll());
|
|
if (minQ.size() - maxQ.size() > 1) {
|
|
maxQ.offer(minQ.poll());
|
|
}
|
|
}
|
|
|
|
public double findMedian() {
|
|
return minQ.size() == maxQ.size() ? (minQ.peek() + maxQ.peek()) / 2.0 : minQ.peek();
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Your MedianFinder object will be instantiated and called as such:
|
|
* MedianFinder obj = new MedianFinder();
|
|
* obj.addNum(num);
|
|
* double param_2 = obj.findMedian();
|
|
*/
|