如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。
import java.util.Comparator; import java.util.PriorityQueue; public class Solution { /首先定义一个 最小堆 即升序 PriorityQueue<Integer> minHeap=new PriorityQueue(); /接着定义一个 最大堆 即降序 PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(21,new Comparator<Integer>(){ public int compare(Integer o1,Integer o2){ return o2-o1; } }); int count=0; public void Insert(Integer num) { if(count%2==0){ /当为偶数的时候,插入小根堆 maxHeap.offer(num); int max=maxHeap.poll(); minHeap.offer(max); }else{ 当为奇数时候,插入大根堆 minHeap.offer(num); int min=minHeap.poll(); maxHeap.offer(min); } count++; } public Double GetMedian() { if(count%2==0){ return new Double(maxHeap.peek()+minHeap.peek())/2; }else{ return new Double(minHeap.peek()); } } }