295 Find Median from Data Stream

Leetcode

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

---

用两个堆来存放数据，一个大顶堆存放小元素，一个小顶堆存放大元素。维持两个堆平衡，要么元素相等，要么小元素的堆比大元素的多一个。插入的时候，如果两个堆元素相等，说明应该插入小元素的堆，否则应该插入大元素的堆。但是不是直接插入，而是先插入另一个堆，然后从其中弹出一个元素插入本来该插入的堆，这样可以维持所有小元素的堆的元素比大元素的堆中的元素小。中间值，如果连个堆相等，则为两个堆堆顶元素的平均，否则为小元素堆的堆顶元素。

空间复杂度 o(n)，插入时间复杂度 o(logn) ，求平均数时间复杂度 o(1)

class MedianFinder {
    PriorityQueue<Integer> small;
    PriorityQueue<Integer> big;
    boolean even;

    public MedianFinder() {
        small=new PriorityQueue<>((i1,i2)->i2-i1);
        big=new PriorityQueue<>();
        even=true;
    }
    
    public void addNum(int num) {
        if(even){
            big.add(num);
            small.add(big.poll());
        } else {
            small.add(num);
            big.add(small.poll());
        }
        even=!even;
        
    }
    
    public double findMedian() {
        if(even){
            return (double)(small.peek()+big.peek())/2;
        } else {
            return (double) small.peek();
        }
    }
}

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