题目描述：

JZ41 数据流中的中位数

思路1：lower_bound

使用 lower_bound 函数，每次都是有序插入

时间复杂度（插入时）：O($n^{2}n^2$)，空间复杂度：O(n)

class Solution {
  private:
    vector<double> vv;
  public:
    void Insert(int num) {
        if(vv.size() == 0) vv.push_back(num);
        else {
            auto it = lower_bound(vv.begin(), vv.end(), num);
            vv.insert(it, num);
        }
        // sort(vv.begin(), vv.end()); // O(nlogn)
    }

    double GetMedian() {
        int len = vv.size();
        if (len & 1) {
            // odd
            int mid = len >> 1;
            return (vv[mid]);
        } else {
            int mid = len >> 1;
            return ((vv[mid - 1] + vv[mid]) / 2);
        }
    }

};

思路2：优先队列

使用两个堆，一个大顶堆，一个小顶堆

• 优先将数插入到大顶堆，在判断当前两个堆的长度差是否大于一，否则，将大顶堆的堆顶push到小顶堆里。具体在两个堆的储存形式就是，小于大顶堆堆顶的数储存在大顶堆，而大于大顶堆堆顶的数储存在小顶堆，如此，如果，num长度是奇数，则中位数是大顶堆堆顶，否则，就是两个堆堆顶除以2.

时间复杂度（插入时）：O($lognlogn$)，空间复杂度：O(n)

class Solution {
public:
  	priority_queue<int, vector<int>, less<>> heapMin; // 大顶堆
  	priority_queue<int, vector<int>, greater<>> heapMax; // 小
  
  	void Insert(int num) {
      	if (heapMin.empty() ||  num < heapMin.top()) {
          	heapMin.push(num);
          	if (heapMax.size() + 1 < heapMin.size()) {
              	heapMax.push(heapMin.top());
              	heapMin.pop();
            }
        } else {
          	heapMax.push(num);
          	if (heapMax.size() > heapMin.size()) {
              	heapMin.push(heapMax.top());
              	heapMax.pop();
            }
        }
    }
  
  	double GetMedian() {
      	if (heapMin.size() > heapMax.size()) {
          	return heapMin.top();
        } else {
          	return (heapMin.top() + heapMax.top()) / 2.0;
        }
    }
}

思路3: 有序集合 + 双指针

待续。。。。。

😿😿😿😿