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

数据流中的中位数

http://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

堆的做法:

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

[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;
    }

};
全部评论

相关推荐

沉淀一会:1.同学你面试评价不错,概率很大,请耐心等待; 2.你的排名比较靠前,不要担心,耐心等待; 3.问题不大,正在审批,不要着急签其他公司,等等我们! 4.预计9月中下旬,安心过节; 5.下周会有结果,请耐心等待下; 6.可能国庆节前后,一有结果我马上通知你; 7.预计10月中旬,再坚持一下; 8.正在走流程,就这两天了; 9.同学,结果我也不知道,你如果查到了也告诉我一声; 10.同学你出线不明朗,建议签其他公司保底! 11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
恰好,我就是有一个弟弟。这样的关注让我感到有些无奈,难道这和我的能力、经验有什么关系吗?求职的路上,真是充满了各种奇怪的考量,让我很想吐槽。希望未来的招聘能更关注求职者的专业素养,而不是这些无关紧要的个人信息。
热血的蚊不叮追赶太阳:找工作,你就是牛马,牛马是否便宜,是否好压迫,女的牛马生不生孩子,男的牛马有没有房贷,一切都是试探你是否好压榨,所以真的我看你是汽车行业的,可以去外企博世,舍弗勒,索恩格,大陆。。。各种外企的供应链 甚至麦当劳苹果店长这些我感觉都把人当人看
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务