题解 | #随时找到数据流的中位数#

题目：随时找到数据流的中位数
描述：有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。
[要求]

如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)
每行有一个整数opt表示操作类型
若opt=1，则接下来有一个整数N表示将N加入到结构中。
若opt=2，则表示询问当前所有数的中位数

示例1：输入：[[1,5],[2],[1,3],[2],[1,6],[2],[1,7],[2]]，返回值：[5,4,5,5.5]
说明：
第一次查询时结构内的数为：5
第二次查询时结构内的数为：3 5
第二次查询时结构内的数为：3 5 6
第二次查询时结构内的数为：3 5 6 7

解法一：
思路分析：首先通过题目来分析，题目中最重要的语句为当 $opt = 1$ 时，就将接下来的整数N加入到结构当中，当 $opt = 2$ 时，表示询问当前所有数的中位数（按顺序排列的一组数据中居于中间位置的数），主要通过这两个1，2操作来实现中位数的获取。
在求中位数的过程中，我们可以设定两个堆结构，一个大根堆，一个小根堆，然后通过将接收到的所有数的较小的一半放入大根堆，将较大的一半放入小根堆，如果接收的个数为奇数，中位数就是小根堆和大根堆中元素多的那个堆的堆顶，例如，当接收到的数组元素为1、8、5、6、4、2、3，小根堆存放的是1234，大根堆存放的是568，小根堆的元素多，所以它的堆顶元素就是该序列的中位数，即4，如果接收的个数为偶数，中位数就是两个堆顶相加除以2。
在具体操作的时候，每当接收到一个数，就需要正确的选择存放的对象，当小于小根堆的时候，就存入大根堆里，否则的话就存入到小根堆，如果出现一个堆的元素比另一个堆的元素多两个的情况，就将前面的堆的堆顶元素弹出添加到后面的堆中，重新调整两个堆，总之，应该始终保持两个堆数量之间的绝对值不能超过1。
实例分析：输入 $[[1,5],[2],[1,3],[2],[1,6],[2],[1,7],[2]]$
图片说明
　　
Python核心代码：

import heapq
#
# the medians
# @param operations int整型二维数组 ops
# @return double浮点型一维数组
#
class Solution:
    def flowmedian(self , operations ):
        # write code here
        #大小不好区分，添加正负号替换
        big = []#大堆栈
        small = []#小堆栈
        res = []#存储地址
        for i in operations:
            if(i[0] == 1):#代表加入元素
                num = i[1]
                if small == [] or num >= small[0]:
                    heapq.heappush(small, num)#将num插入small中
                else:
                    heapq.heappush(big, -num)#否则就插入到big中
                if len(small) - len(big) > 1:
                    heapq.heappush(big, -heapq.heappop(small))#把small中的栈顶元素给了big
                if len(big) - len(small) > 1:
                    heapq.heappush(small, -heapq.heappop(big))#把big中的栈顶元素给了small
            if i[0] == 2:#代表求中位数
                if len(small) == 0 and len(big) == 0:#没有元素，返回-1
                    res.append(-1)
                elif len(small) > len(big):#输出small中的栈顶元素
                    res.append(small[0])
                elif len(small) < len(big):#输出big中的元素
                    res.append(-big[0])
                else:#否则的话除2取中位数
                    res.append((small[0]-big[0])/2)
        return res

因为随时能够知道中间位置的两个数是多少，所以取得中位数的时间复杂度为 $O(1)$ ，同时根据堆的性质，向堆中添加新的数，并调整，所以其总的时间复杂度为 $O(logN)$ 。需要额外的内存空间用来存储值，所以空间复杂度为 $O(N/2 + N/2 + i) = O(N + i)$ ，其中i为 $opt = 2$ 的操作次数，N为插入数的数量。

解法二：
思路分析：通过上一个步骤的分析，我们明白了取中位数可能发生的三种条件：
1、当元素只有一个的时候，就可以直接返回该元素充当中位数。
2、当插入元素的时候，需要比较，为偶数的时候，需要将中间的两个元素相加除以2便是中位数的大小值。为奇数的时候，可以直接返回中间位置的元素值充当中位数。
3、我们还可以按照平衡树的方法，当插入的数比当前中位数大，说明，中位数可能后移，如果比当前中位数小，说明中位数可能前移。
根据上述方法，我们可以形成两个独立的函数，add函数和findmid函数，通过首先判断第一个元素是否为1，如果为1，就进行add添加函数，如不为1，就进行findmid寻找中位数函数。
C++核心代码为：

class Solution {
public:
    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    multiset<int> s;//按照特定顺序存储元素的容器,其中元素是可以重复的
    multiset<int>::iterator mid;//定义一个中位数的模板容器
    vector<double> flowmedian(vector<vector<int> >& operations) {
        // write code here
        vector<double> res;//存储的对象
        for (auto & i : operations) {
            if (i[0] == 1)
                add(i[1]);//代表需要添加元素
            else
                res.push_back(findmid());//将返回的中间值存放到res容器当中
        }
        return res;
    }

     void add(int num) {
        int len = s.size();//首先判断S的大小
        s.insert(num);//添加进去
        if (len == 0)
            mid = s.begin();
        else {
            //比较中位数和新插入数的大小，进行相应的前移/后移
            if (num < *mid)
                mid = (len & 1) ? prev(mid) : mid;//prev为上一个中位数
            else
                mid = (len & 1) ? mid : next(mid);
        }
    }

    double findmid() {
        if (!s.size()) 
            return -1;
        if (s.size() & 1)
            return *mid;
        else {
            return (*mid + *next(mid)) / 2.0;
        }
    }
};

根据上面代码分析可得，只需要判断第一个元素是否为1即可，所以其时间复杂度为 $O(N)$ ，N为 $opt = 1$ 和 $opt = 2$ 的个数和。其在内存空间方面，扩展了额外的内存空间，所以其空间复杂度为 $O(N)$ ，其中N为 $opt = 2$ 的个数。