295. Find Median from Data Stream

Posted on | Edited on | Views:

LeetCode

Two Heaps

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
26
27
28
29
30
31
class MedianFinder {
    PriorityQueue<Integer> minheap=null;
    PriorityQueue<Integer> maxheap=null;

    /** initialize your data structure here. */
    public MedianFinder() {
        minheap=new PriorityQueue<>();
        maxheap=new PriorityQueue<>(Collections.reverseOrder());
    }
    
    public void addNum(int num) {
        if(maxheap.isEmpty()||num<maxheap.peek()){
            maxheap.offer(num);
        }else minheap.offer(num);
        if(Math.abs(maxheap.size()-minheap.size())<=1) return;
        if(maxheap.size()>minheap.size()) minheap.offer(maxheap.poll());
        else maxheap.offer(minheap.poll());
    }
    
    public double findMedian() {
        if(maxheap.size()>minheap.size()) return maxheap.peek();
        else if(minheap.size()>maxheap.size()) return minheap.peek();
        return (double)(maxheap.peek()+minheap.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();
 */

0%