题解 | #数据流中的中位数# 基于官方题解的逻辑整理

#include <functional>
#include <queue>
#include <vector>
class Solution {
public:
    priority_queue<int> left;
    priority_queue<int,vector<int>,greater<int>> right;
    void Insert(int num) {
        right.push(num);
        // 此时代码缺少“排序”的逻辑，所以出问题，如何用两个优先队列实现排序？
        // 排序
        left.push(right.top());
        right.pop();
        right.push(left.top());
        left.pop();

        if(right.size() > left.size()+1){
            left.push(right.top());
            right.pop();
        }
    }

    double GetMedian() { 
        if(right.size() > left.size()){
            return right.top();
        }else{
            return (double)((double)left.top() + (double)right.top())/2;
        }
    }

};

基于牛客官方的题解，但是感觉自己理解起来比较困难，在此整理思路：

首先是通过两个“优先队列”的数据结构实现寻找中位数的逻辑，具体实现时需要考虑的问题有：

1、如何正确地实现两个优先队列的逻辑功能。

2、如何在两个优先队列的基础上判断返回值的逻辑。

首先考虑第一个逻辑问题：这两个队列希望实现的逻辑是一个保存了现有输入的较小的一部分并且能返回该部分的最大值（为了中位数），另外一个保存另外（较大）的一部分并返回其中的最小值。那么如何实现呢？

我想到的是针对新加入的一个数，它可能会导致两个队列的变化，即针对一个新的输入如何调整两个队列，使得他们各自实现各自的逻辑功能？如果新加入的值属于较大的这一部分，那么直接加入right即可，如果是较小的那一部分，需要将其和left部分的最大值位置替换。所以有了排序那部分代码。这样就成功维持了两个优先队列。

其次考虑第二个问题：中位数的判断和输入个数是奇数还是偶数有关，所以这个逻辑需要在代码的某些属性上体现出来，自然地想到两个队列包含的元素个数。

具体实现就是通过维持两个队列的个数实现，如果总数是奇数，一定会有一个队列的元素个数比另外一个多的情况出现，如果是偶数，根据中位数的概念应该是排序后的中间两个数取平均。

基于这种逻辑那么元素个数的逻辑就清晰起来了，即偶数时两个队列元素个数相同，奇数的时候一个并另外一个多1。具体实现就是通过判断两个队列的元素个数执行对应的调整代码。