資訊專欄INFORMATION COLUMN
摘要：思路和代碼這里采用了兩個優(yōu)先隊(duì)列來實(shí)現(xiàn)。一個優(yōu)先隊(duì)列用來存儲字符流中較小的一半，另一個用來存儲字符流中數(shù)值較大的一半。這樣當(dāng)需要獲取當(dāng)前中位數(shù)時，就可以根據(jù)當(dāng)前的數(shù)值個數(shù)選擇一個或是兩個數(shù)的平均值。
題目要求
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
這里需要我們設(shè)計(jì)一個數(shù)據(jù)結(jié)構(gòu)，使得我們可以從當(dāng)前的字符流中獲取中位數(shù)。
思路和代碼這里采用了兩個優(yōu)先隊(duì)列來實(shí)現(xiàn)。一個優(yōu)先隊(duì)列用來存儲字符流中較小的一半，另一個用來存儲字符流中數(shù)值較大的一半。這樣當(dāng)需要獲取當(dāng)前中位數(shù)時，就可以根據(jù)當(dāng)前的數(shù)值個數(shù)選擇一個或是兩個數(shù)的平均值。
private PriorityQueueminQueue; 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; } }
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68772.html
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...
摘要：建立兩個堆，一個堆就是本身，也就是一個最小堆另一個要寫一個，使之成為一個最大堆。我們把遍歷過的數(shù)組元素對半分到兩個堆里，更大的數(shù)放在最小堆，較小的數(shù)放在最大堆。同時，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...
摘要：最大堆存的是到目前為止較小的那一半數(shù)，最小堆存的是到目前為止較大的那一半數(shù)，這樣中位數(shù)只有可能是堆頂或者堆頂兩個數(shù)的均值。我們將新數(shù)加入堆后，要保證兩個堆的大小之差不超過。最大堆堆頂大于新數(shù)時，說明新數(shù)將處在所有數(shù)的下半部分。 Data Stream Median 最新更新：https://yanjia.me/zh/2019/02/... Median is the middle v...
摘要：題目鏈接這題和那道比起來多加了個。還是用兩個來做，這個操作復(fù)雜度用了。和，在保存較小的一半元素，保存較大的一半元素，，注意寫的時候不能用，因?yàn)榭赡?。沒想出來其他方法，參考的解法 480. Sliding Window Median 題目鏈接：https://leetcode.com/problems... 這題和那道Find Median from Data Stream比起來多加了個...
摘要：窗口前進(jìn)，刪隊(duì)首元素保證隊(duì)列降序加入當(dāng)前元素下標(biāo)從開始，每一次循環(huán)都將隊(duì)首元素加入結(jié)果數(shù)組 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...
閱讀 2340·2021-11-22 14:56
閱讀 1479·2021-09-24 09:47
閱讀 913·2019-08-26 18:37
閱讀 2832·2019-08-26 12:10
閱讀 1528·2019-08-26 11:55
閱讀 3150·2019-08-23 18:07
閱讀 2306·2019-08-23 14:08
閱讀 612·2019-08-23 12:12
