📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : 无限输入流取中数

🔗
CStick75 2012-9-6 16:13:45 | 只看该作者
全局:
两个堆吧 = - = 一个大顶一个小顶……然后维护两个堆的size一样大,并且第一个的堆顶不大于第二个的堆顶
每次新来一个元素就跟当前的堆顶比较
然后要维护两种情况 第一种是 两个堆一样大(总共有偶数个元素) 第二种是两个堆一样大并且有一个额外的元素(总共有奇数个元素)
第一种情况来了一个元素的话就跟 两个堆顶比较 如果在两个堆顶元素之间就放着,否则如果新元素小于大顶堆的堆顶,就pop小顶堆的堆顶然后新元素插入小顶堆
第二种情况的话就是 如果额外的元素比新元素大,那么新元素进大顶,老的进小顶,否则的话就反过来
然后这样查询O(1) 维护O(lgN)
回复

使用道具 举报

🔗
285845348 2012-10-9 05:23:08 | 只看该作者
全局:
大小堆一起用
另外extractMaxMin操作相对来说不算多,f堆效率会比b堆好
回复

使用道具 举报

🔗
CharlesW 2012-12-31 15:42:24 | 只看该作者
全局:
本帖最后由 CharlesW 于 2012-12-31 15:53 编辑

刚写了一个:

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

#include <vector>
using std::vector;

#include <queue>
using std::priority_queue;

#include <functional>
using std::greater;

int main(int argc, char* argv[])
{
        int number = 0;
        float median = 0;
        priority_queue<int> max_heap;
        priority_queue<int, vector<int>, greater<int> > min_heap;

        while(cin >> number) {
                if (max_heap.empty() && min_heap.empty()) {
                        max_heap.push(number);
                        median = number;
                } else {
                        if (number <= max_heap.top()) {
                                max_heap.push(number);
                                if (max_heap.size() - min_heap.size() > 1) {
                                        min_heap.push(max_heap.top());
                                        max_heap.pop();
                                }
                        } else {
                                min_heap.push(number);
                                if (min_heap.size() > max_heap.size()) {
                                        max_heap.push(min_heap.top());
                                        min_heap.pop();
                                }
                        }
                        if (max_heap.size() > min_heap.size()) {
                                median = max_heap.top();
                        } else {
                                median = (max_heap.top() + min_heap.top()) / 2.0;
                        }
                }
                cout << "current median: " << median << endl;
        }
  1. }
复制代码

回复

使用道具 举报

🔗
ilhrx 2013-1-25 10:19:56 | 只看该作者
全局:
median of median 能否在这上面用。。。。但主要是无限输入输出流,有点棘手
回复

使用道具 举报

🔗
monkeylyf 2013-2-9 07:58:17 | 只看该作者
全局:
点了下传送门看了下lz签名里的博客
题目好多阿 可惜似乎没有对题目的描述 虽然大部分题目都做过 不过看到没做过的题目和一个简单的标题 就很难理解题意了。。
回复

使用道具 举报

🔗
longsail 2013-7-21 16:06:01 | 只看该作者
全局:
怎么有些解答看不到的,请版主告知下,谢谢
回复

使用道具 举报

🔗
longsail 2013-7-21 16:10:24 | 只看该作者
全局:
Imbalism 发表于 2011-4-26 15:25
我的解法:
    维护两个堆hLarge(最小堆)和hLess(最大堆)还有一个变量median,hLarge堆里所有元素的值 ...

看不懂啊,讲解更细致就好了
回复

使用道具 举报

🔗
wntdjmhh 2013-7-28 14:03:15 | 只看该作者
全局:
可以使用经过改进过的二叉排序树,树的根结点表示其中数。定义树为中数平衡,当且仅当树根结点的左子树的结点数=右子树结点数或右子树结点数+1时。初始的时候,根结点为第一个元素。然后,依照二叉排序数的算法,依次加入元素,若二叉树不中数平衡,则调节使其中数平衡。若左边的结点数大于右边的结点数+1,则取根结点左子树的最大值,做为最的中点。右边亦然,则每次取中数,其时间复杂度为log(n)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表