题目

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

题解

有三种方法

1. 插入排序法

在插入每一个数时使用插入排序的思路，这样在取数的时候只需要取中间的数（奇数）或者中间两数的平均数（偶数）。
注意插入时使用了upper_bound()，这是函数找到最后一个匹配数的下一个迭代器，或者插入不影响升序。
理论上用upper_bound会更快一些，插入时移动的数字较少。

lower_bound和upper_bound。这两个操作都接受一个关键字，返回一个迭代器。如果关键字在容器中，lower_bound 返回的迭代器将指向第一个具有给定关键字的元素，而upper_bound返回的迭代器则指向最后一个匹配给定关键字的元素之后的位置。如果元素不在multimap 中，则lower_bound 和upper_bound 会返回相等的迭代器一—指向一个不影响排序的关键字插入位置。
——c++ primer 第五版

  • 时间复杂度：插入$O(n)+O(logn)$，插入时移动数组与二分查找。
    取数$O(1)$
  • 空间复杂度$O(n)$，保存数组
class MedianFinder {//三种方法。1.插入排序法
    vector<int> nums;//定义数组
public:
    /** initialize your data structure here. */
    MedianFinder() {}
    
    void addNum(int num) {
        if(nums.empty()) nums.push_back(num);//为空直接加入num
        else nums.insert(upper_bound(nums.begin(), nums.end(), num),num);//不为空进行插入排序，用upper_bound比lower_bound要移动的数字少
    }
    
    double findMedian() {
        int n = nums.size();
        //分正负取中位数
        return n & 1? nums[n/2] : (nums[n/2-1]+nums[n/2])*0.5;//用0.5而不是/2来取小数部分
    }
};

2. 两堆法

这个方法利用了堆的性质，在c++中是priority_queue，建立一个大顶堆存小的半部分，一个小顶堆放大的半个部分，注意存数时不能直接存，详见注释

  • 时间复杂度：插入$O(logn)$，插入堆消耗，其他操作都是$O(1)$。
    取数$O(1)$
  • 空间复杂度$O(n)$，保存两个堆
class MedianFinder {//三种方法。2.两堆法
    priority_queue<int, vector<int>, less<int> > lo;//大顶堆存小的一半的数字
    priority_queue<int, vector<int>, greater<int> > hi;//小顶堆存大的一半的数字
public:
    /** initialize your data structure here. */
    MedianFinder() {}
    
    void addNum(int num) {
        //若两个堆数字数量相等，总数为偶数，此时需要将数字加入hi
        //但是不能直接加，因为有可能num属于lo，需要将num加入lo，再把堆顶push给hi
        //这里的条件判断起到了平衡两个堆的作用
        if(lo.size() == hi.size()){
            lo.push(num);
            hi.push(lo.top());
            lo.pop();
        }
        //当两个堆数字数量不等，总数为奇数时需要将num加入lo，操作与上面类似，只是相反
        else{
            hi.push(num);
            lo.push(hi.top());
            hi.pop();
        }
    }
    
    double findMedian() {
        //用0.5而不是/2，这样才能取float
        return lo.size()==hi.size()? (lo.top()+hi.top())*0.5 : hi.top();
    }
};

3. 红黑树法（multiset）

也可以直接用自平衡二叉搜索树的性质，multiset的底层实现是红黑树，符合我们的要求（set中不能有重复数组，因此需要用multiset），再定义一个迭代器指针指向中位数（奇数）或中间偏后的数（偶数）即可，每次插入只需要判断奇偶和输入的数属于哪半边，更新迭代器的指向即可，具体更新见注释。根据奇偶输出中位数即可

  • 时间复杂度：插入$O(logn)$
  • 空间复杂度：$O(n)$
class MedianFinder {//三种方法。3.红黑树法（multiset）
    multiset<int> nums;//定义mutliset存数组
    multiset<int>::iterator mid;//定义指向中位数的指针
public:
    /** initialize your data structure here. */
    //这里用委托构造函数初始化mid的值，相比于在构造函数内部初始化效率更高
    MedianFinder():mid(nums.end()){}
    
    void addNum(int num) {
        const int n = nums.size();//用const int存数组长度
        nums.insert(num);//插入新数
        //注意n是插入num之前的multiset长度
        //只有一个数的时候，mid为这个数
        if(!n) mid = nums.begin();
        //当num为前半段的数时，判断n的奇偶
        //若n为奇数，+1为偶数，mid不变，指向中间偏后的数
        //若n为偶数，+1为奇数，指向前一个数，即当前的中位数
        else if(num < *mid) mid = n&1? mid : prev(mid);
        //当num为后半段的数时，判断n的奇偶
        //若n为奇数，+1为偶数，mid指向后一个数，指向中间偏后的数
        //若n为偶数，+1为奇数，mid不变，即当前的中位数
        else n&1? mid = next(mid) : mid;
    }
    
    double findMedian() {
        const int n = nums.size();
        //取中位数的时候判断奇偶，奇数直接取mid，偶数取mid和前一个数
        return n&1? *mid : (*mid+*prev(mid))*0.5;
        //也可以这么输出
        //return (*mid + *next(mid, n%2-1))*0.5;
    }
};