295. 数据流的中位数

 

class MedianFinder {Queue<Integer> A,B;public MedianFinder() {A = new PriorityQueue<>();//小根堆存储后半部分B = new PriorityQueue<>((x,y)->(y-x));//大根堆存储前半部分}public void addNum(int num) {if(A.size()==0 && B.size()==0){B.add(num);//这个要returnreturn;};if(num<=B.peek()){B.add(num);}else{A.add(num);}if(Math.abs(B.size()-A.size()) >= 2){if (B.size() > A.size()) {A.add(B.poll());} else {B.add(A.poll());}}}public double findMedian() {if(A.size()==B.size()){return (A.peek()+B.peek()) / 2.0;}else{return A.size() > B.size() ? A.peek() : B.peek();}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

 

class MedianFinder {Queue<Integer> A,B;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() : (A.peek()+B.peek()) / 2.0;}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/