解题报告：LeetCode Find Median from Data Stream（查找中位数）

题目来源： https://leetcode.com/problems/find-median-from-data-stream/

题目描述：实现一个能插入数据和查询当前中位数的数据结构。

输入输出：输入输出格式请查看题目链接。

解题思路：

1，首先，一个很简单粗暴的想法是直接用vector储存数据并在每次查询时调用algorithm库中的sort函数进行排序，然后输出可直接输出中间值或中间值的平均数作为中位数。代码如下：

class MedianFinder {
public:
    std::vector<int> numbers;

    MedianFinder():sum(0),n(0){};

    // Adds a number into the data structure.
    void addNum(int num) {
       numbers.push_back(num);
    }

    // Returns the median of current data stream
    double findMedian() {
        int n = numbers.size();
        sort(&(numbers[0]), &(numbers.back());
        return (numbers[n/2]+numbers[(n-1)/2])/2;
    }
};

2，不出意外，这段代码超时了，于是我们需要优化一下。一个很自然的想法是仍然使用vector存储数据，每次插入之后直接进行插入排序即可。代码如下：

const int maxn = 100000;
class MedianFinder {
public:
    int numbers[maxn];
    int n;

    MedianFinder():n(0){};

    // Adds a number into the data structure.
    void addNum(int num) {
        int pos = n-1;
        n ++;
        while(pos >= 0 && numbers[pos] > num)
        {
            numbers[pos+1] = numbers[pos];
            pos --;
        }
        numbers[pos+1] = num;
    }

    // Returns the median of current data stream
    double findMedian() {
         return (numbers[n/2]+numbers[(n-1)/2])/(double)2;
    }
};

为了避免频繁的插入导致vector重新分配空间，上述代码使用了一个静态数组以解决这个问题。这段代码虽然很简单，但是出乎意料的是它AC了。虽然时间比较长。

3，问题解决了之后，我将上述代码改为用vector存储数据，结果果断超时。再加上上述代码复杂度稍高，于是决定想出一种比较快速的方法。仔细回想这道题的要求，我们需要在插入后对数据进行排序，但是自己写的插入排序复杂度还是稍微高了一点，于是我们可以想到stl里面的很多的有自带排序的模板类，如set，priority_queue等。此外，我们只需要关心数据中的中间一个或两个元素。一种比较简单的办法是将输入数据分为两部分，一部分储存不大于中位数的数，一部分储存不小于中位数的数，且动态维持两部分中的数据规模不大于一即可。顺着这个思路，我们可以写出如下的代码（如下代码中使用了priority_queue作为容器来储存数据，且left队列中使用了系统自带的less比较模板类，以实现数据从小到大排序，right数组中使用了自定义的compare类，以实现数据从大到小的排序。）：

  struct compare  
 {  
   bool operator()(const int& l, const int& r)  
   {  
       return l > r;  
   }  
 };  
class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> left;
    priority_queue<int, vector<int>, compare> right;

    // Adds a number into the data structure.
    void addNum(int num) {
        if(left.size() == right.size())
        {
            if(right.size() && num > right.top())
            {
                int num_temp = right.top();
                right.pop();
                right.push(num);
                left.push(num_temp);
            }
            else
                left.push(num);
        }
        else
        {
            if(num < left.top())
            {
                int num_temp = left.top();
                left.pop();
                left.push(num);
                right.push(num_temp);
            }
            else
                right.push(num);
        }

    }

    // Returns the median of current data stream
    double findMedian() {
         return (left.size()==right.size() ? (left.top()+right.top())/double(2) : left.top());
    }
};