|
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，[2,3,4]?的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
这道题的引用思想是大堆和小堆。因为它们可以定位最大值和最小值，即可以定位有序列表的中间两个数。比较有意思的就是PriorityQueue函数在这类题中有着很好的效果。
PriorityQueue?实际上是一个堆（不指定Comparator时默认为最小堆），通过传入自定义的Comparator函数可以实现大顶堆。
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>(){ //大顶堆，容量11
@Override
public int compare(Integer i1,Integer i2){
return i2-i1;
}
}
?而上述方法又可以用lambda表达式来进行简化。
Lambda 表达式，也可称为闭包，它是推动 Java 8 发布的最重要新特性。
Lambda 允许把函数作为一个方法的参数（函数作为参数传递进方法中）。
使用 Lambda 表达式可以使代码变的更加简洁紧凑。
/*
min存放的是中位数左边的数值，用的最大堆进行排列，顶放的是中位数左边的最大值。
max与之相反。
*/
class MedianFinder {
PriorityQueue<Integer>min;
PriorityQueue<Integer>max;
/** initialize your data structure here. */
public MedianFinder() {
min = new PriorityQueue<>((a, b)->(b - a));
max = new PriorityQueue<>();
}
/*
每次来一个新的值，我们首先将它放在最大堆进行一次排序，排序后将堆顶放入右边再次排序，这样就可以确定这个值的位置。最后判断两边是否失衡。即右边的值的数量不能大于左边。
*/
public void addNum(int num) {
min.add(num);
max.add(min.remove());
if(max.size() > min.size()) min.add(max.remove());
}
public double findMedian() {
if(min.size() == max.size())
return (max.peek() + min.peek())/2.0;
else return min.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
?待补充python，今晚没时间了。。。
|