剑指offer JZ63

数据流中的中位数

https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&&tqId=11216&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

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

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库用起来很爽, 看来要好好学习下。

全部评论

相关推荐

06-04 19:10
门头沟学院 Java
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务