63、数据流中的中位数 值得再看

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

1、自己的想法与做法
class Solution {
public:
    void Insert(int num)
    {
        result.push_back(num);
    }

    double GetMedian()
    {
        sort(result.begin(), result.end());
        int len = result.size();
        if (len % 2 == 0) 
            return (result[len / 2] + result[-1 + len / 2]) / 2.0//注意这里是2.0 这样才能返回值为double
        else
            return result[len / 2];
    }

    vector<int> result;
};
2、借助两个堆，非常精妙的方法
这里讨论两种方法：
一：代码复杂：减少不必要插入，提高效率
二：代码大大简化：可能有不必要插入，效率有所降低
==============思路解析=================================
思考：如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
一：代码复杂：
* 分析：对于海量数据和流的数据，用最大堆和最小堆来管理
* 我们希望 数据分为[小]|[大]两个部分，细化一点
[最大堆 |   左边最大 leftMax]
右边最小rightMin | 最小堆]


* 定义一个规则：保证左边和右边个数相差不大于1，且左边小于右边
* 1.数据是偶数的时候 insert的数据进入 [右边，最小堆]中
*  1.1当插入的数字cur > leftMax时，直接插入到[右边，最小堆]中
*  1.2当插入的数字cur < leftMax时，为了保证左边小于右边，
*      先把cur插入[最大堆|左边最大leftMax]中，
*      然后把leftMax放入[右边最小rightMin|最小堆]中
*      就可以保证： 左边 < 右边
* 2.数据是奇数的时候 insert的数据进入 [左边，最大堆]中
*      2.1当插入的数字cur < rightMin时，直接插入到[左边，最小堆]中
*      2.2当插入的数字cur > rightMin时，为了保证左边小于右边，
*      先把cur插入[右边最小rightMin|最小堆]中，
*      然后把rightMin放入[最大堆|左边最大leftMax]中
*      就可以保证： 左边 < 右边
* 最后：
* 如果是偶数：中位数mid= (leftMax+right)/2
* 如果是奇数：中位数mid= leftMax 因为先插入到左边，再插入到右边，为奇数时，中位数就是mid
class Solution {

public:
void Insert(int num)
    {
    count += 1; //数据是奇数的时候 insert的数据进入 [左边，最大堆]中
    if (count % 2 == 1)//奇数
    {
        if (big_heap.empty())  big_heap.push(num); //直接插入到[左边，最小堆]中
        else {
            int rightMin = small_heap.top();
            if (num <= rightMin)  big_heap.push(num);
            else {
                small_heap.push(num);  //先把cur插入[右边最小rightMin|最小堆]中
                big_heap.push(rightMin);  //然后把rightMin放入[最大堆|左边最大leftMax]中
                small_heap.pop();
            }
        }
    }
    else {

        if (small_heap.empty()) { //当第一个元素 比 第二个元素大的时候，会造成左边比右边大的情形，因此要加上判断
//当第一个数据比第二个大的时候，比如[5,2,3,4,1,6,7,0,8]的情况，会造成最大堆的唯一数据，比最小堆的唯一数据大的情况，这跟思想就不同了，因此需要加上一层判断。
            if (num > big_heap.top())
            {
                small_heap.push(num);
            }
            else
            {
                small_heap.push(big_heap.top());
                big_heap.pop();
                big_heap.push(num);
            }
        }
        else {
            int leftMax = big_heap.top();
            if (num >= leftMax)  small_heap.push(num);//直接插入到[右边，最小堆]中
            else {
                big_heap.push(num);//先把cur插入[右边最小rightMin|最小堆]中，
                small_heap.push(big_heap.top()); //然后把rightMin放入[最大堆|左边最大leftMax]中
                big_heap.pop();
            }
        }
    }        
}

double GetMedian()
{
    if (count & 0x1) {//看见这个0x你肯定知道这就是16进制表示了，而0x1就是最后一位肯定是1。偶数的二进制表示