LeetCode——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

設計資料結構存儲資料流并能找出資料流的中位數。
思路：首先找中位數是需要對資料流進行排序的。但是這裡不是一次給出所有資料，而是逐漸累加。是以要維護一個有序數列。
首先想到的是Java中的SortedSet可以維護有序集，但是在擷取中位數的時候必須要轉換成數組，才能直接擷取到中位數，時間複雜度較大。逾時。
      

class MedianFinder {
    
    private int count;
    private int sum;
    private java.util.SortedSet<Integer> set;
    
    public MedianFinder() {
        set = new TreeSet();
    }

    // Adds a number into the data structure.
    public void addNum(int num) {
        set.add(num);
    }

    // Returns the median of current data stream
    public double findMedian() {
        Integer[] list = set.toArray(new Integer[0]);
        int size = set.size();
        double res = 0.0;
        if(size % 2 == 0) {
            res = (double)(list[size/2] + list[size/2 - 1]) / 2.0;
        }
        else {
            res = (double)list[size/2];
        }
        return res;
    }
};

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

然後看到網上有用優先隊列實作的，思路是這樣的，維護兩個優先隊列，其實内部是用堆實作的。維護一個大頂堆，一個小頂堆。分别存儲資料流中較大的一般和較小的一半。如果資料流的總數是奇數那麼大頂堆中的個數要多一個，這樣一來在擷取中位數的時候，對于資料流總數是奇數的情況直接傳回大頂堆堆頂，對于資料流總數是偶數的情況傳回兩個堆頂的平均數。最重要的是要維護兩個堆的大小。在優先隊列中offer，poll時間複雜度為O(logn) peek時間複雜度為O(1)，是以addNum的時間複雜度為O(logn),findMedian時間複雜度為O(1)。

public class MedianFinder {
    
    private Queue<Integer> maxHeap; //大頂堆
    private Queue<Integer> minHeap; //小頂堆
    
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<Integer>(11,Collections.reverseOrder());
        minHeap = new PriorityQueue<Integer>();
    }
    
    
    public void addNum(int num) {
        //插入大頂堆
        if(maxHeap.size()==0 || maxHeap.peek()>=num) {
            maxHeap.offer(num);
            if(maxHeap.size()-1 > minHeap.size()) {
                minHeap.offer(maxHeap.poll());
            }
        }
        //插入小頂堆
        else if(minHeap.size()==0 || minHeap.peek() < num) {
            minHeap.offer(num);
            if(minHeap.size() > maxHeap.size()) {
                maxHeap.offer(minHeap.poll());
            }
        }
        //兩者之間，先考慮大頂堆。
        else {
            if(maxHeap.size() <= minHeap.size()) {
                maxHeap.offer(num);
            }
            else {
                minHeap.offer(num);
            }
        }
        
        
    }
    
    
    
    public double findMedian() {
        if(maxHeap.size() == minHeap.size()) {
            return (double)(maxHeap.peek() + minHeap.peek()) / 2.0;
        }
        else {
            return (double)maxHeap.peek();
        }
    }
    
    
}