中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-median-from-data-stream
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
import java.util.Comparator;
import java.util.PriorityQueue;
class MedianFinder {
private PriorityQueue<Integer> leftQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Integer.compare(o2, o1);
}
});
private PriorityQueue<Integer> rightQueue = new PriorityQueue<>();
public MedianFinder() {
}
public void addNum(int num) {
if (leftQueue.isEmpty() || num <= leftQueue.peek()) {
leftQueue.offer(num);
while (leftQueue.size() > rightQueue.size() + 1) {
rightQueue.offer(leftQueue.poll());
}
} else {
rightQueue.offer(num);
while (rightQueue.size() > leftQueue.size()) {
leftQueue.offer(rightQueue.poll());
}
}
}
public double findMedian() {
int length = leftQueue.size() + rightQueue.size();
if (length % 2 == 0) {
return (leftQueue.peek() + rightQueue.peek()) / 2.0;
} else {
return leftQueue.peek();
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/