[LeetCode]Find Median from Data Stream

suemi 發布于2019-08-14 15:08 / 1081人閱讀

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

分析

這道題的經典做法就是維護兩個Heap, 一個MaxHeap, 一個MinHeap，維護他們的size，比如保證

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

當然這種題可以有些follow up, 比如：

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

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

復雜度

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());
        
        // 維護兩個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();

GPU云服務器云服務器 Median LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65328.html

leetcode295. Find Median from Data Stream

摘要：思路和代碼這里采用了兩個優先隊列來實現。一個優先隊列用來存儲字符流中較小的一半，另一個用來存儲字符流中數值較大的一半。這樣當需要獲取當前中位數時，就可以根據當前的數值個數選擇一個或是兩個數的平均值。題目要求 Median is the middle value in an ordered integer list. If the size of the list is even, t...

microcosm1994 2019-08-15 14:42 評論0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立兩個堆，一個堆就是本身，也就是一個最小堆另一個要寫一個，使之成為一個最大堆。我們把遍歷過的數組元素對半分到兩個堆里，更大的數放在最小堆，較小的數放在最大堆。同時，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 評論0 收藏0
[Leetcode] Find Median from Data Stream 數據流中位數

摘要：最大堆存的是到目前為止較小的那一半數，最小堆存的是到目前為止較大的那一半數，這樣中位數只有可能是堆頂或者堆頂兩個數的均值。我們將新數加入堆后，要保證兩個堆的大小之差不超過。最大堆堆頂大于新數時，說明新數將處在所有數的下半部分。 Data Stream Median 最新更新：https://yanjia.me/zh/2019/02/... Median is the middle v...

heartFollower 2019-08-14 12:28 評論0 收藏0
480. Sliding Window Median

摘要：題目鏈接這題和那道比起來多加了個。還是用兩個來做，這個操作復雜度用了。和，在保存較小的一半元素，保存較大的一半元素，，注意寫的時候不能用，因為可能。沒想出來其他方法，參考的解法 480. Sliding Window Median 題目鏈接：https://leetcode.com/problems... 這題和那道Find Median from Data Stream比起來多加了個...

Scorpion 2019-08-16 10:28 評論0 收藏0
[LintCode/LeetCode] Sliding Window Maximum/Median

摘要：窗口前進，刪隊首元素保證隊列降序加入當前元素下標從開始，每一次循環都將隊首元素加入結果數組 Sliding Window Maximum Problem Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration fro...

crelaber 2019-08-14 14:33 評論0 收藏0