📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3049| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

请教大神们算法题关于Top K最频繁变动的股价

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
就是不断有股票价格进来,要实时按顺序show出变动最频繁的Top K只股票代码
我看有人说维护一个size 大小为K的min heap,但是show的时候需要pop K次吧,每次pop时间是LogK,那么show K个元素的复杂度就是KLogK吧,而且要把heap里面的元素都pop出来,然后还要再push回去吧,总觉得这应该不是最优方案吧?
请教各位大神们
谢谢!

评分

参与人数 1大米 +2 收起 理由
的萨菲 + 2 很有用的信息!

查看全部评分


上一篇:坐标南湾,求组队刷题
下一篇:你们都好厉害,只想找个和我一样刚开始刷题的,从头开始学习,慢慢提高吧
🔗
 楼主| michaellm 2017-4-26 10:41:22 | 只看该作者
全局:
刚想了想,觉得应该维护一个 binary search tree 比较好些,不知道有没有更好的算法
回复

使用道具 举报

🔗
风的风格 2017-4-26 12:31:05 | 只看该作者
全局:
参考这个 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148682&ctid=274
回复

使用道具 举报

🔗
 楼主| michaellm 2017-4-26 13:07:13 | 只看该作者
全局:
感谢!
是说那个帖子里面的第5题吧

5. Top K int in a large stream (This can be done in O(n))
补充内容 (2015-11-20 08:17):
第五题O(N)解法: 2K windows, Quick Select, throw K away.

但是我感觉股票这道题还不太一样的地方就是随着新数据进来,之前check过的数据有可能是要更新的,而上面那道题check过之后就丢弃了,有点给定一个数组找出top K元素的意思,数组一旦给定就是静态数据了。但是股票这个是动态数据
回复

使用道具 举报

🔗
风的风格 2017-4-26 14:54:37 | 只看该作者
全局:
那题也一样,粗暴一点除了heap外需要维持一个频率的map,那题map大小为int最大值,这题map大小为上市公司数量
回复

使用道具 举报

🔗
haveto 2017-4-26 15:16:15 | 只看该作者
全局:
size balanced tree
回复

使用道具 举报

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

本版积分规则

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