295. Find Median from Data Stream!

two PriorityQueue

class MedianFinder {

    // min heap
    // java defaul priority queue is min heap
    // use min heap to keep large numbers
    PriorityQueue<Integer> large = new PriorityQueue<>();
    // use max heap to store small numbers
    PriorityQueue<Integer> small = new PriorityQueue<>((a,b)->b-a);
    /** initialize your data structure here. */
    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        // make small.size()>=large.size();
        if(small.size()>large.size()){
            //method: offer
            large.offer(num);
        }else{
            small.offer(num);
        }
        
        if(small.size() >0 && large.size()>0 && small.peek()>large.peek()){
            int temp=small.poll();
            small.offer(large.poll());
            large.offer(temp);
        }
    }
    
    public double findMedian() {
        if(small.size()==large.size()){
            // convert to float
            return (small.peek()+large.peek())/2.0;
        }else{
            return small.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

follow-up question:

Follow up:

• If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

• If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

Answer:

1

-we maintain HashMap -we also maintain total number of elements, so that median is just total-nums/2 th element from sorted array.

-then we go over Map from 1-100 and count element, when we hit total-nums/2 th element , that is our median

2.

add two variable to count the numbers that smaller and larger than 100 respectively.