Data Stream Median Summary (Leetcode 295, Lintcode 81, Lintcode 360)

這類題是一類典型的two priority queue的題目累贤。維護(hù)兩個(gè)heap狱杰,一個(gè)MinHeap差凹,一個(gè)MaxHeap看疙。本解法中豆拨,MaxHeap的在奇數(shù)時(shí)會(huì)多一個(gè),奇數(shù)時(shí)返回MaxHeap的top(注意這里面的邏輯能庆,如果先往MaxHeap放施禾,那么MaxHeap就一定要多一個(gè))。另外注意搁胆,c++此題直接用multiset來實(shí)現(xiàn)priority_queue弥搞。如果priority_queue里面裝的是int,直接用multiset了

Leetcode 295:

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        size = 0;
    }
    
    void addNum(int num) {
        size++;
        if(m1.empty() || num < *m1.begin()){
            m1.insert(num);
        }
        else{
            m2.insert(num);
        }
        if(m1.size() > m2.size() + 1){
            m2.insert(*m1.begin());
            m1.erase(m1.begin());
        }
        
        if(m2.size() > m1.size()){
            m1.insert(*m2.begin());
            m2.erase(m2.begin());
        }
    }
    
    double findMedian() {
        if(size % 2 == 0){
            return (*m1.begin() + *m2.begin()) / 2.0;
        }
        else{
            return *m1.begin();
        }
    }
private:
    multiset<int, greater<int>> m1; // max heap
    multiset<int> m2; // min heap
    int size;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

Lintcode 81:
Lintcode的題目要求稍有不同渠旁。偶數(shù)個(gè)時(shí)攀例,不是除平均,而是返回小的那個(gè)數(shù)顾腊。

 class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: the median of numbers
     */
    void insertNumber(int num){
        if(max_heap.empty() || num < *max_heap.begin()){
            max_heap.insert(num);
        }
        else{
            min_heap.insert(num);
        }
        
        if(max_heap.size() > min_heap.size() + 1){
            min_heap.insert(*max_heap.begin());
            max_heap.erase(max_heap.begin());
        }
        
        if(min_heap.size() > max_heap.size()){
            max_heap.insert(*min_heap.begin());
            min_heap.erase(min_heap.begin());
        }
        
    }
    
    vector<int> medianII(vector<int> &nums) {
        // write your code here
        vector<int> ret;
        if(nums.empty()) return ret;
        
        for(auto it : nums){
            insertNumber(it);
            ret.push_back(*max_heap.begin());
        }
        return ret;
    }
private:
    multiset<int, greater<int>> max_heap;
    multiset<int> min_heap;
};

Lintcode 360: Sliding Window Median

這道題也是用維護(hù)兩個(gè)heap來求解粤铭。難點(diǎn)在于要維護(hù)一個(gè)size = k的window,而不考慮其它元素杂靶。

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of the element inside the window at each moving
     */
    void insert(int num){
        if(m1.empty() || num <= *m1.begin()){
            m1.insert(num);
        }else{
            m2.insert(num);
        }
        balanceSet();
    } 
    
    void balanceSet(){
        if(m1.size() > m2.size() + 1){
            int cur = *m1.begin();
            m1.erase(m1.begin());
            m2.insert(cur);
        }
        if(m2.size() > m1.size()){
            int cur = *m2.begin();
            m2.erase(m2.begin());
            m1.insert(cur);
        }
    }
     
    void erase(int num){
        if(num <= *m1.begin()){
            m1.erase(m1.find(num));
        }else{
            m2.erase(m2.find(num));
        }
        balanceSet();
    } 
    vector<int> medianSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        vector<int> ret;
        if(nums.empty() || k <= 0) return ret;
        int idx = min(k, (int)nums.size());
        for(int i=0; i<idx; i++){
            insert(nums[i]);
        }
        ret.push_back(*m1.begin());
        for(int i=idx; i<nums.size(); i++){
            erase(nums[i - k]);
            insert(nums[i]);
            ret.push_back(*m1.begin());
        }
        return ret;
    }
private:
    multiset<int, greater<int>> m1;
    multiset<int> m2;
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末梆惯,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子吗垮,更是在濱河造成了極大的恐慌垛吗,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件烁登,死亡現(xiàn)場(chǎng)離奇詭異怯屉,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)饵沧,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門锨络,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人狼牺,你說我怎么就攤上這事羡儿。” “怎么了锁右?”我有些...
    開封第一講書人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長讶泰。 經(jīng)常有香客問我咏瑟,道長,這世上最難降的妖魔是什么痪署? 我笑而不...
    開封第一講書人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任码泞,我火速辦了婚禮,結(jié)果婚禮上狼犯,老公的妹妹穿的比我還像新娘余寥。我一直安慰自己领铐,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開白布宋舷。 她就那樣靜靜地躺著绪撵,像睡著了一般。 火紅的嫁衣襯著肌膚如雪祝蝠。 梳的紋絲不亂的頭發(fā)上音诈,一...
    開封第一講書人閱讀 52,785評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音绎狭,去河邊找鬼细溅。 笑死,一個(gè)胖子當(dāng)著我的面吹牛儡嘶,可吹牛的內(nèi)容都是我干的喇聊。 我是一名探鬼主播,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼蹦狂,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼誓篱!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起鸥咖,我...
    開封第一講書人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤燕鸽,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后啼辣,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體啊研,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年鸥拧,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了党远。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡富弦,死狀恐怖沟娱,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情腕柜,我是刑警寧澤济似,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站盏缤,受9級(jí)特大地震影響砰蠢,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜唉铜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一台舱、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧潭流,春花似錦竞惋、人聲如沸柜去。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽嗓奢。三九已至,卻和暖如春胰挑,著一層夾襖步出監(jiān)牢的瞬間蔓罚,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來泰國打工瞻颂, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留豺谈,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓贡这,卻偏偏與公主長得像茬末,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子盖矫,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容