题解 | #数据流中的中位数#

堆的做法：

中位数是指：有序数组中中间的那个数。则根据中位数可以把数组分为如下三段:

[0 ... median - 1], [median], [median ... arr.size() - 1]，即[中位数的左边，中位数，中位数的右边]

那么，如果我有个数据结构保留[0...median-1]的数据，并且可以O(1)时间取出最大值，即arr[0...median-1]中的最大值 相对应的，如果我有个数据结构可以保留[median + 1 ... arr.size() - 1] 的数据， 并且可以O(1)时间取出最小值，即 arr[median + 1 ... arr.size() - 1] 中的最小值。 然后，我们把[median]即中位数，随便放到哪个都可以。

假设[0 ... median - 1]的长度为l_len, [median + 1 ... arr.sise() - 1]的长度为 r_len.

1. 如果l_len == r_len + 1, 说明，中位数是左边数据结构的最大值
2. 如果l_len + 1 == r_len, 说明，中位数是右边数据结构的最小值
3. 如果l_len == r_len, 说明，中位数是左边数据结构的最大值与右边数据结构的最小值的平均值。

定义：priority_queue<Type, Container, Functional>

Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式。

当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

class Solution {
public:
    priority_queue<int> max_pq;//默认大顶堆，降序
    priority_queue<int, vector<int>, greater<int>> min_pq;
    void Insert(int num) {
        if(!max_pq.size() || max_pq.top() >= num)
            max_pq.push(num);
        else
            min_pq.push(num);
        if(max_pq.size() > min_pq.size() + 1){
            min_pq.push(max_pq.top());
            max_pq.pop();
        }
        else if(max_pq.size() + 1 < min_pq.size()){
            max_pq.push(min_pq.top());
            min_pq.pop();
        }
    }

    double GetMedian() { 
        if(max_pq.size() < min_pq.size())
            return min_pq.top() / 1.0;
        else if(max_pq.size() > min_pq.size())
            return max_pq.top() / 1.0;
        else 
            return (max_pq.top() + min_pq.top()) / 2.0;
    }

};

二分法插入排序：

class Solution {
public:
    vector<int> nums;
    void Insert(int num) {
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(nums[mid] < num)
                l = mid + 1;
            else
                r = mid - 1;
        }
        nums.insert(nums.begin() + l, num);
    }

    double GetMedian() { 
        if(nums.size() % 2)
            return (double)(nums[nums.size() / 2]);
        else
            return ((double)(nums[nums.size() / 2] + nums[nums.size() / 2 - 1])) / 2;
    }

};