题目
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。
思路 + 代码
参考CyC
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| import java.util.*; public class Solution { private PriorityQueue<Integer> left = new PriorityQueue<Integer>((o1, o2)->o2-o1); private PriorityQueue<Integer> right = new PriorityQueue<Integer>(); private int N = 0; public void Insert(Integer num) { if(N%2==0){ left.add(num); right.add(left.poll()); }else{ right.add(num); left.add(right.poll()); } N++; }
public Double GetMedian() { if(N%2==0){ return (left.peek()+right.peek())/2.0; }else{ return (double)right.peek(); } }
|