数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解法

题目本身不难理解，就是从不断增加的数据中找出中位数，因此需要有合适的容器和方法来决定插入的操作和获取中位数的操作；

数组作为容器，直接插入为O(1)，使用快排方式寻找中位数O(n)；
数组作为容器，插入时顺便排序，插入为O(n)，寻找中位数为O(1);
链表作为容器，插入排序为O(n)，寻找中位数为O(1)（两个指针指向中位数）;
二叉搜索树，插入平均为O(logN),最差为O(N),寻找中位数平均为O(logN),最差为O(n)；
最大堆和最小堆，插入为O(logN),寻找中位数为O(1);

解法5的代码

    multiset<int> left;
    multiset<int> right;
    multiset<int>::reverse_iterator ri_left;
    multiset<int>::iterator i_right;
    int all = 0;
    
    void Insert(int num)
    {
        if((all & 1) == 0){ //偶数放左边
            if(left.empty()){
                left.insert(num);
                all++;
                return;
            }
            i_right = right.begin();
            ri_left = left.rbegin();
            //如果新的数小于等于右边最小，插入
            if(*i_right >= num ){ 
                left.insert(num);
                all++;
                return;
            }
            //否则将右边最小插入到左边，并删除原来右边最小，将新的数插入到右边
            left.insert(*i_right);
            right.erase(*i_right);
            right.insert(num);
            all++;
        }else{        //奇数个放右边
            if(right.empty()){
                ri_left = left.rbegin();
                if(*ri_left > num ){
                    right.insert(*ri_left);
                    left.erase(*ri_left);
                    left.insert(num);
                    all++;
                    return;
                }
                right.insert(num);
                all++;
                return;
            }
            //如果新的数大于等于左边最大，插入
            ri_left = left.rbegin();
            i_right = right.begin();
            if(*ri_left <= num){
                right.insert(num);
                all++;
                return;
            }
            //否则将左边最大插入到右边，并删除原来左边最大，将新的数插入到左边
            right.insert(*ri_left);
            left.erase(*ri_left);
            left.insert(num);
            all++;
        }
    }
    
    double GetMedian()
    { 
        ri_left = left.rbegin();
        i_right = right.begin();
        if((all & 1) == 0){
            return ((*ri_left)+(*i_right))/(2.0);
        }else{
            return *ri_left;
        }
    }