295. Find Median from Data Stream - jiejackyzhang/leetcode-note GitHub Wiki

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.

Examples: [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.

For example:

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

解题思路为：考虑数组长度的奇偶性，median为中间数或中间两数的平均值。 因此将数组分成两部分，small和large。 其中small的元素个数为n/2，large的元素个数为n/2或n/2+1。 我们关心的是small的最大值和large的最小值。 因此采用max heap来实现small，min heap来实现large。

每当添加一个新元素时，有两种情形：

length of (small, large) == (k, k)
length of (small, large) == (k, k+1)

加入后，两部分变为

length of (small, large) == (k, k+1)
length of (small, large) == (k+1, k+1)

因此当n为偶数时，我们先将新元素加入small，然后取small中的最大值放入large； 当n为奇数时，我们先将新元素加入large，然后取large中的最小值放入small；

public class MedianFinder {
    
    private PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> large = new PriorityQueue<>();
    boolean even = true;

    // Adds a number into the data structure.
    public void addNum(int num) {
        if(even) {
            small.offer(num);
            large.offer(small.poll());
        } else {
            large.offer(num);
            small.offer(large.poll());
        }
        even = !even;
    }

    // Returns the median of current data stream
    public double findMedian() {
        if(even) {
            return (small.peek() + large.peek()) / 2.0;
        } else {
            return large.peek();
        }
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();
⚠️ **GitHub.com Fallback** ⚠️