[LeetCode]Find Median from Data Stream

suemi 發(fā)布于2019-08-14 15:08 / 1084人閱讀

Find Median from Data Stream

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

分析

這道題的經(jīng)典做法就是維護(hù)兩個(gè)Heap, 一個(gè)MaxHeap, 一個(gè)MinHeap，維護(hù)他們的size，比如保證

MaxHeap.size() - MinHeap.size() >= 1

當(dāng)然這種題可以有些follow up, 比如：

除了heap做，還有什么其他方法？
BST可以，比如可以在Node里增加一個(gè)size表示整個(gè)children的數(shù)量，findMedian時(shí)間復(fù)雜度會(huì)增加到log(n);

如果是找比如處在1/10th的元素，怎么找？
同樣可以用兩個(gè)heap做，維護(hù)一個(gè)的size是另一個(gè)size的1/9即可。

復(fù)雜度

time: addNum -> O(log(n)), findMedian -> O(1)
space: O(n)

代碼

class MedianFinder {

    // Adds a number into the data structure.
    PriorityQueue minHeap = new PriorityQueue();
    PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder());
    
    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.remove());
        
        // 維護(hù)兩個(gè)heap的size 
        if (minHeap.size() > maxHeap.size()) 
            maxHeap.add(minHeap.remove());
    }

    // Returns the median of current data stream
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) 
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        else 
            return maxHeap.peek();
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();