算法1

(大小顶堆) $O(logn)$

将数组分成两半，一个大顶堆和一个小顶堆，大顶堆维护小于中位数的所有元素，小顶堆维护大于中位数的所有元素，两个堆的元素数量差不能超过2，超过2就互相匀一匀。

C++ 代码

class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int,vector<int>,greater<int> > min_heap;
    void insert(int num){
        if(max_heap.size()==0&&min_heap.size()==0){
            max_heap.push(num);
            min_heap.push(num);
            return;
        }


        if (max_heap.top() > num){
            max_heap.push(num);
        }
        else {
            min_heap.push(num);
        }

        if (max_heap.size() - min_heap.size()==2 ){
            max_heap.pop();
            int k = max_heap.top();
            min_heap.push(k);
        }
        else if( max_heap.size() - min_heap.size()==-2){
            min_heap.pop();
            int k = min_heap.top();
            max_heap.push(k);
        }
    }

    double getMedian(){

        if (min_heap.size()==max_heap.size()){
            return min_heap.top();
        }
        else if (min_heap.size() > max_heap.size()){
            int x1 = min_heap.top();
            // cout<<x1<<endl;
            min_heap.pop();
            int x2 = min_heap.top();
            min_heap.push(x1);
            // cout<<x2<<endl;
            return (x1+x2)/2.0;
        }
        else{
            int x1 = max_heap.top();
            max_heap.pop();
            int x2 = max_heap.top();
            max_heap.push(x1);
            return (x1+x2)/2.0;
        }
    }
};