leetcode295. Find Median from Data Stream

microcosm1994 發布于2019-08-15 14:42 / 341人閱讀

摘要：思路和代碼這里采用了兩個優先隊列來實現。一個優先隊列用來存儲字符流中較小的一半，另一個用來存儲字符流中數值較大的一半。這樣當需要獲取當前中位數時，就可以根據當前的數值個數選擇一個或是兩個數的平均值。

題目要求

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:

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

這里需要我們設計一個數據結構，使得我們可以從當前的字符流中獲取中位數。

思路和代碼

這里采用了兩個優先隊列來實現。一個優先隊列用來存儲字符流中較小的一半，另一個用來存儲字符流中數值較大的一半。這樣當需要獲取當前中位數時，就可以根據當前的數值個數選擇一個或是兩個數的平均值。

    private PriorityQueue minQueue;
    private PriorityQueue maxQueue;
    /** initialize your data structure here. */
    public MedianFinder () {
        minQueue = new PriorityQueue();
        maxQueue = new PriorityQueue();
    }
    
    public void addNum(int num) {
        maxQueue.add((long)num);
        minQueue.add(-maxQueue.poll());
        if(maxQueue.size() < minQueue.size()){
            maxQueue.add(-minQueue.poll());
        }
        
    }
   
    public double findMedian() {
        if(maxQueue.size() > minQueue.size()){
            return maxQueue.peek();
        }else{
            return ( maxQueue.peek() - minQueue.peek() ) / 2.0;
        }
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

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

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

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

[LeetCode]Find Median from Data Stream

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. Examp...

suemi 2019-08-14 15:08 評論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