295. Find Median from Data Stream (1)

Link

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.

• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it? bucket sort, array with size 101 to record the counter

2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it? same idea, add two counters to record less_than_zero and more_than_hundrend

Solution

Concept: 用兩個PriorityQueue只保留一半的value並以minHeap maxHeap的方式呈現

ex1:

input: 12345

pq1(min heap) : 543 -> (當nums有奇數個時，讓min Heap size = maxHeap size + 1)

pq2(max heap): 12

ex2:

input: 1234

pq1(min heap): 43

pq2(max heap): 12

class MedianFinder {

    /** initialize your data structure here. */
    PriorityQueue<Integer> minHeap;
    PriorityQueue<Integer> maxHeap;
    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>((a,b)-> Integer.compare(b,a));
    }
    
    public void addNum(int num) {
        minHeap.add(num);
        maxHeap.add(minHeap.poll()); //這個步驟在確保minHeap中的最小>= maxHeap中的最大       
        if(minHeap.size() < maxHeap.size()){
            minHeap.add(maxHeap.poll());
        }
    }
    
    public double findMedian() {
        return (minHeap.size() == maxHeap.size()) ? 
            ((double)maxHeap.peek() + minHeap.peek()) / 2: minHeap.peek();
    }
}