思路
针对本题,根据以上思路,可以将数据流保存在一个列表中,并在添加元素时 保持数组有序 。此方法的时间复杂度为 O(N)O(N) ,其中包括: 查找元素插入位置 O(\log N)O(logN) (二分查找)、向数组某位置插入元素 O(N)O(N) (插入位置之后的元素都需要向后移动一位)。
本题可以借助堆来进行优化
建立一个小顶堆A和大顶堆B,各自保存列表元素的一半,规定:
随后,中位数可根据A,B的堆顶元素计算得到。
整体流程
实现代码(java)
class MedianFinder {
Queue<Integer> A, B;
/** initialize your data structure here. */
public MedianFinder() {
A = new PriorityQueue<>();
B = new PriorityQueue<>((x, y) -> (y - x));
}
public void addNum(int num) {
if (A.size() != B.size()) {
A.add(num);
B.add(A.poll());
} else {
B.add(num);
A.add(B.poll());
}
}
public double findMedian() {
return A.size() != B.size() ? A.peek() * 1.0 : (A.peek() + B.peek()) / 2.0;
}
}
细节解释
Queue<Integer> A, B;
A = new PriorityQueue<>();
B = new PriorityQueue<>((x, y) -> (y - x));
这两句代码的含义是,定义一个A为优先队列,默认就是按照自然顺序排列的小顶堆,最小的元素排在最前面
而下一行的B则为修改了比较规则的大顶堆,相当于将小顶堆倒转过来,大的元素排在前面
可以替换为:B = new PriorityQueue<>(Comparator.reverseOrder())