面试 Python canal安装 dataframe validation extjs plugins node uicollectionview rss vue响应式 管理后台模板 河南网络推广 sql数据库教学视频 mysql当前时间减一天 bootstrap图表 nginx默认端口号 matlab四舍五入 查看mysql是否启动 eclipse显示左边目录 python的编译器 javapackage java数组输出 java命令 python网站开发实例 acmecadconverter 离散数学pdf max电池容量 emit 8元秒电脑 mathcad15 怎么设置迅雷为默认下载器 ppt格式刷怎么用 c4d挤压怎么用 子节点 男网红头像 sqlprompt 珊瑚版 华为杂志锁屏怎么设置 lol世界第一
当前位置: 首页 > 学习教程  > 编程语言

Leetcode 剑指 Offer 41. 数据流中的中位数

2020/11/24 9:32:14 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。 例如, [2,3,4] 的中位数是 3…

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1:

输入:
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]
示例 2:

输入:
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]

限制:

最多会对 addNum、findMedian 进行 50000 次调用。

方法一:左手一个大顶堆 + 右手一个小顶堆。

解题思路

  1. 我们没有必要把所有数据进行排序。只需要保证数据左半边的数都小于右半边的数,那么根据左半边的数的最大值及右半边的数的最小值即可得到中位数。
  2. 若输入的数据个数是奇数,比如 1、2、3、4、5。我们可以把左边的 1、2 存入一个大顶堆中,把右边的 3、4、5 存入一个小顶堆中。那么中位数就是小顶堆的 top()。
  3. 若输入的数据个数是偶数,比如 1、2、3、4。我们可以把左边的 1、2 存入一个大顶堆中,把右边的 3、4 存入一个小顶堆中。那么中位数就是两个堆的 top() 的和再乘 0.5。
  4. 整个过程我们需要维护两个地方:两个堆的 size() 最大只能相差 1;大顶堆的 top() 必须小于等于小顶堆的 top()。

实现方法

  1. 每插入一个数之前,先判断两个堆的 size() 是否相等。
  2. 若相等,先将这个数插入大顶堆,然后将大顶堆的 top() 插入小顶堆。这么做可以保证小顶堆的所有数永远大于等于大顶堆的 top()。
  3. 若不相等,先将这个数插入小顶堆,然后将小顶堆的 top() 插入小顶堆。这么做可以保证大顶堆的所有数永远小于等于小顶堆的 top()。
  4. 整个过程我们都动态地做到了平衡两个堆的 size(),即保证它们的 size() 最大只相差了 1。

结果输出

  1. 若最后两个堆的 size() 不等。由于当两个堆的 size() 相等时我们总是选择将数插入小顶堆中(先插入大顶堆但马上又将大顶堆的 top() 插入小顶堆),所以中位数一定是小顶堆的 top()。比如数据是 1、2、3、4、5,最后大顶堆中是 1、2,小顶堆中是 3、4、5,中位数是小顶堆的 top()。
  2. 若最后两个堆的 size() 相等。那么中位数就是两个堆的 top() 的和再乘 0.5。
#include<iostream>
#include<queue>
#include<vector>

using namespace std;

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int, vector<int>, less<int> > maxheap;//大顶堆按从大到小排列,队头(pop)元数最大
    priority_queue<int, vector<int>, greater<int> > minheap;//小顶堆按从小到大排列,队头(pop)元数最小

    MedianFinder() {

    }
    
    void addNum(int num) {
        if(maxheap.size() == minheap.size()) {
            maxheap.push(num);
            minheap.push(maxheap.top());
            maxheap.pop();
        }
        else {
            minheap.push(num);
            maxheap.push(minheap.top());
            minheap.pop();
        }
    }
    
    double findMedian() {
        int maxSize = maxheap.size(), minSize = minheap.size();
        if(maxSize==0) return NULL;
        int mid1 = maxheap.top(), mid2 = minheap.top();
        return maxSize == minSize ? ((mid1 + mid2) * 0.5) : mid2;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

int main()
{   
    int num[]={1,2,3};
    double param_2;
    MedianFinder* obj = new MedianFinder();
    param_2 = obj->findMedian();
    cout<<param_2<<endl;
    obj->addNum(num[0]);
    obj->addNum(num[1]);
    param_2 = obj->findMedian();
    cout<<param_2<<endl;
    obj->addNum(num[2]);
    param_2 = obj->findMedian();
    cout<<param_2<<endl;
    system("pause");
    return 0;
}

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_400053.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?