Find Median from Data Stream Solutions in C++

// Source : https://leetcode.com/problems/find-median-from-data-stream/
// Author : Hao Chen
// Date   : 2015-11-14




class MedianFinder {
    
private:
    //we seprate the sorted array to two parts
    multiset<int> first, second;
    
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        if (first.empty() || num <= *(first.rbegin()) ) {
            first.insert(num);
        } else {
            second.insert(num);
        }
        
        if (first.size() > second.size() + 1) {
            auto it = first.end();
            it--;
            second.insert(*(it));
            first.erase(it);
        }
        
        if ( first.size() < second.size() ) {
            first.insert(*(second.begin()));
            second.erase(second.begin());
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        if (first.size()> second.size()) {
            return *(first.rbegin());
        }
        double x = *first.rbegin();
        double y = *second.begin();
        return (x+y)/2;
    }
};

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

/// https://leetcode.com/problems/find-median-from-data-stream/
/// Author : liuyubobobo
/// Time   : 2019-09-22

#include <iostream>
#include <vector>

using namespace std;


/// Insertion Sort
/// Time Complexity: add: O(n)
///                  findMedian: O(1)
class MedianFinder {

private:
    vector<int> data;

public:
    /** initialize your data structure here. */
    MedianFinder() {}

    void addNum(int num) {

        data.push_back(num);

        int i;
        for(i = (int)data.size() - 1; i >= 1 && data[i] > data[i - 1]; i --)
            swap(data[i], data[i - 1]);
    }

    double findMedian() {

        if(data.size() % 2) return data[data.size() / 2];
        return (data[data.size() / 2 - 1] + data[data.size() / 2]) / 2.0;
    }
};


int main() {

    MedianFinder mf;
    mf.addNum(6);
    cout << "after adding 6 :" << mf.findMedian() << endl; // 6

    mf.addNum(10);
    cout << "after adding 10 :" << mf.findMedian() << endl; // 8

    mf.addNum(2);
    cout << "after adding 2 :" << mf.findMedian() << endl; // 6

    mf.addNum(6);
    cout << "after adding 6 :" << mf.findMedian() << endl; // 6

    mf.addNum(5);
    cout << "after adding 5 :" << mf.findMedian() << endl; // 6

    mf.addNum(0);
    cout << "after adding 0 :" << mf.findMedian() << endl; // 5.5

    mf.addNum(6);
    cout << "after adding 6 :" << mf.findMedian() << endl; // 6.0

    mf.addNum(3);
    cout << "after adding 3 :" << mf.findMedian() << endl; // 5.5

    return 0;
}

/// https://leetcode.com/problems/find-median-from-data-stream/
/// Author : liuyubobobo
/// Time   : 2019-09-22

#include <iostream>
#include <map>

using namespace std;


/// Using TreeMap
/// Time Complexity: add: O(logn)
///                  findMedian: O(logn)
class MedianFinder {

private:
    map<int, int> data;
    int count = 0;

    map<int, int>::iterator iter;
    int index = 0;

public:
    /** initialize your data structure here. */
    MedianFinder() {}

    void addNum(int num) {

        if(!count){
            data[num] ++;
            iter = data.begin();
            count ++;
            return;
        }

        data[num] ++;
        if(count % 2){ // odd number
            if(num < iter->first){
                if(index) index --;
                else iter --, index = iter->second - 1;
            }
        }
        else{ // even number
            if(num >= iter->first){
                if(index + 1 < iter->second) index ++;
                else iter ++, index = 0;
            }
        }
        count ++;
    }

    double findMedian() {

        if(count % 2) return iter->first;

        if(index + 1 < iter->second) return iter->first;

        map<int, int>::iterator iter2 = iter;
        iter2 ++;
        return (iter->first + iter2->first) / 2.0;
    }
};


int main() {

    MedianFinder mf;
    mf.addNum(6);
    cout << "after adding 6 " << mf.findMedian() << endl; // 6

    mf.addNum(10);
    cout << "after adding 10 " << mf.findMedian() << endl; // 8

    mf.addNum(2);
    cout << "after adding 2 " << mf.findMedian() << endl; // 6

    mf.addNum(6);
    cout << "after adding 6 " << mf.findMedian() << endl; // 6

    mf.addNum(5);
    cout << "after adding 5 " << mf.findMedian() << endl; // 6

    mf.addNum(0);
    cout << "after adding 0 " << mf.findMedian() << endl; // 5.5

    mf.addNum(6);
    cout << "after adding 6 " << mf.findMedian() << endl; // 6.0

    mf.addNum(3);
    cout << "after adding 3 " << mf.findMedian() << endl; // 5.5

    return 0;
}

/// https://leetcode.com/problems/find-median-from-data-stream/
/// Author : liuyubobobo
/// Time   : 2019-09-23

#include <iostream>
#include <map>
#include <queue>

using namespace std;


/// Two Priority Queue
/// Time Complexity: add: O(logn)
///                  findMedian: O(logn)
class MedianFinder {

private:
    priority_queue<int> left; // maxheap
    priority_queue<int, vector<int>, greater<int>> right; // minheap

public:
    /** initialize your data structure here. */
    MedianFinder() {}

    void addNum(int num) {

        if(!left.size() && !right.size()){
            left.push(num);
            return;
        }

        if((left.size() + right.size()) % 2){ // odd
            if(num >= left.top()) right.push(num);
            else{
                right.push(left.top());
                left.pop();
                left.push(num);
            }
        }
        else{ // even
            if(num <= right.top()) left.push(num);
            else{
                left.push(right.top());
                right.pop();
                right.push(num);
            }
        }
    }

    double findMedian() {

        if((left.size() + right.size()) % 2) return left.top();
        return (left.top() + right.top()) / 2.0;
    }
};


int main() {

    MedianFinder mf;
    mf.addNum(40);
    cout << "after adding 40 : " << mf.findMedian() << endl; // 40

    mf.addNum(12);
    cout << "after adding 12 : " << mf.findMedian() << endl; // 26

    mf.addNum(16);
    cout << "after adding 16 : " << mf.findMedian() << endl; // 16

    return 0;
}