Find Median from Data Stream

Problem

Find Median from Data Stream

Approach

1. The 1st approach is to Sort all the numbers every time it’s needed to add a new number to the array.
2. (2nd approach) There are too much time wasting in sorting. So, we can use InsertSort to reduce the time complexity. How to get the position of the new element? It’s efficient to use Binary Search.
3. There is also a more efficient approach, Heap. We can maintain two heaps to tackle the problem. And the first heap, max heap, is used to record these elements who are smaller than the median and the second heap, min heap, is used to record these who are larger than the median.

Why are there one min heap and one max heap?

Firstly, as for the max heap, if the total number of elements are odd, the top of the heap is the answer. Then, as for the min heap, it only receives elements from elements popped from the max heap and if so, it can keep the state that all elements in itself are larger than the median.

Code

// approach 2
class MedianFinder {
    private List<Integer> nums;
    /** initialize your data structure here. */
    public MedianFinder() {
        nums = new ArrayList<>();
    }
    
    private int findLeftMostPos(int target){
        int L = 0, R = this.nums.size() - 1;
        while(L <= R){
            int mid = (R - L)/2 + L;
            if(this.nums.get(mid) >= target){
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return L;
    }
    
    public void addNum(int num) {
        int pos = findLeftMostPos(num);
        if(pos >= this.nums.size()){
            nums.add(num);
        } else {
            nums.add(pos, num);
        }
    }
    
    public double findMedian() {
        int size = this.nums.size();
        if(size % 2 == 0){
            return (1.0 * nums.get(size / 2) + nums.get(size / 2 - 1)) / 2.0;
        } else {
            return nums.get(size / 2);
        }
    }
}

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

 // appoarch 3
 class MedianFinder {
    PriorityQueue<Integer> maxHeap, minHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return b - a;
            }
        });
        minHeap = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return a - b;
            }
        });
    }
    
    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        if(maxHeap.size() < minHeap.size()){
            maxHeap.add(minHeap.poll());
        }
    }
    
    public double findMedian() {
        int cnt = minHeap.size() + maxHeap.size();
        if(cnt % 2 == 0){
            return (1.0 * minHeap.peek() + maxHeap.peek()) / 2.0;
        }
        return maxHeap.peek();
    }
}

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