295. Find Median from Data Stream Hard 6150114Add to ListShare

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints:

• -105 <= num <= 105
• There will be at least one element in the data structure before calling findMedian.
• At most 5 * 104 calls will be made to addNum and findMedian. 

解法： 一个大顶堆（存前半段元素），一个小顶堆（存后半段元素），那么取中位数只需要从堆顶取即可

时间复杂度：

Follow up:

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

解法：可以直接开个int[100]数组，插入元素进行count[i]++, 查找的时候根据count找到最终的中位数 ，插入和查找 都为O(1) 

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

解法：可以把数据分3段：  x < 0 (使用maxheap), x in 0 ~ 100 （使用数组count）, x > 100  （使用minheap）

class MedianFinder {
    private PriorityQueue<Integer> minHeap;
    private PriorityQueue<Integer> maxHeap;
    
    public MedianFinder() {
        minHeap = new PriorityQueue<Integer>((x,y)->x-y);//小顶堆，存后半段
        maxHeap = new PriorityQueue<Integer>((x,y)->y-x);//大顶堆，存前半段
    }
    
    public void addNum(int num) {//O(logN)
        if(maxHeap.isEmpty() || maxHeap.peek()>num) maxHeap.offer(num);//如果小于大顶堆top，放前半段
        else minHeap.offer(num);//否则放后半段
        //保持两堆数量平衡，或者大顶堆多一个
        while(minHeap.size()>maxHeap.size()) maxHeap.offer(minHeap.poll());
        while(minHeap.size()<maxHeap.size()-1) minHeap.offer(maxHeap.poll());
    }
    
    public double findMedian() {//O(1)
        //如果数量一样，去各自头取平均
        if(minHeap.size()==maxHeap.size()) return ((double)minHeap.peek()+(double)maxHeap.peek())/2;
        //奇数个直接去大顶堆top，因为奇数时肯定大顶堆元素多一个
        return maxHeap.peek();
    }
}