剑指offer JZ63

题目描述：数据流的中位数。
题目要求实现一个插入操作，和返回中位数的操作。
这里插入后要时时排序， 并索引中位数， 整个算法可以从一下角度思考：
插入灵活（数组|链表|等）+排序复杂度低+索引迅速。
首先先用暴力法走一遍流程（数组（插入开销大 但 索引迅速）+冒泡（简单））

class Solution {
public:
    vector<int> arr;
    void Insert(int num) {
        arr.push_back(num);
    }
    double GetMedian() {
        //----自带sort算法
        sort(arr.begin(), arr.end());
        int len = arr.size();
        if (len & 1 ){
            return double(arr[len >> 1]);
        }else{
            return double(arr[len >> 1] + arr[(len-1) >> 1]) /2 ; 
        }
    }
};

使用自己的冒泡排序

class Solution {
public:
    vector<int> arr;
    void Insert(int num) {
        arr.push_back(num);
    }

    double GetMedian() {
        //----自带sort算法
        //sort(arr.begin(), arr.end());
        //----自己写sort:冒泡
        int len = arr.size();
        int tmp = 0;
        for(int i=0; i<len; i++)
            for(int j =0; j<len-i-1; j++)
                if(arr[j] > arr[j+1]){
                    tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp;
                }
        if (len & 1 ){
            return double(arr[len >> 1]);
        }else{
            return double(arr[len >> 1] + arr[(len-1) >> 1]) /2 ; 
        }
    }
};

至此， 已经可以发现， 想要优化， 就应当思考不同排序算法的效率，以及数据形式，是否易于插入， 索引。
我自己想到一个改进是利用插入排序， 因为插入排序可以在插入时就维护好数组升序， 从而返回中位数时只要索引即可。这样的排序的复杂度每次是O（N）。

class Solution {
public:
    vector<int> arr;
    void Insert(int num) {
        if(arr.empty())
            arr.push_back(num);
        else{
            //自带的插入
            auto it = lower_bound(arr.begin(),arr.end(),num);
            arr.insert(it, num);
        }
    }

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

自己的插入写法：

class Solution {
public:
    vector<int> arr;
    void Insert(int num) {
       arr.push_back(num);
        int i=0;
       for(i = arr.size()-1; i>0; i--)
           if(num < arr[i-1])     
               arr[i] = arr[i-1];
           else
               break;
        arr[i] = num;
    }

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

如果考虑到数据结构和排序算法的结合：
1、数组：插入困难， 索引容易
2、链表： 插入简单， 索引困难；
3、树：存储有序， 方便索引，排序调整。
这里具体我也不太熟悉， 刚开始学习， 后期会优化， 这里给出大小顶堆的方法：
如果对于中位数左侧利用大顶堆， 则左侧升序， 对右侧利用小顶堆， 则右侧有序， 这样方便插入，排序， 以及返回中位数。

class Solution {
public:
    priority_queue<int> min_q;
    priority_queue<int, vector<int>, greater<int>> max_q;
    void Insert(int num) {
        //若一开始两个堆长度相同，平衡后仍然相同
        min_q.push(num);
        max_q.push(min_q.top());
        min_q.pop();
        //左小于右， 左右差1， 将mid维护到左（大）堆中去
        if(min_q.size()< max_q.si***_q.push(max_q.top());
            max_q.pop();
        }
    }

    double GetMedian() {
        //return min_q.size() > max_q.size()? double(min_q.top()):double(min_q.top()+max_q.top())/2;
        if(min_q.size()>max_q.size())
            return double(min_q.top());
        else
            return double(min_q.top() + max_q.top())/2;
    }
};

果然STL库用起来很爽， 看来要好好学习下。