免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 求m个数中取n个最大数的高效算法
12下一页
最近访问板块 发新帖
查看: 8655 | 回复: 13
打印 上一主题 下一主题

求m个数中取n个最大数的高效算法 [复制链接]

wishel

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2010-07-15 17:04 |只看该作者 |倒序浏览
m个数，取n个最大，结果不需要排序，m很大，n远小于m。
wishel

论坛徽章:
0
2楼 [报告]
发表于 2010-07-15 17:06 |只看该作者
回复 1# wishel

另外，stl里有没有现成可用的东西，省的我自己写啦，呵呵
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
没本

论坛徽章:
0
3楼 [报告]
发表于 2010-07-15 17:20 |只看该作者
std::map或者std::set
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
donglongchao

论坛徽章:
0
4楼 [报告]
发表于 2010-07-15 17:53 |只看该作者
std::map或者std::set
没本 发表于 2010-07-15 17:20

正解，往里扔就是了。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
anbutu

论坛徽章:
0
5楼 [报告]
发表于 2010-07-15 18:00 |只看该作者
大根堆
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
wishel

论坛徽章:
0
6楼 [报告]
发表于 2010-07-15 18:03 |只看该作者
汗死，3楼4楼的朋友，要害死我啊
m的值是几千万
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
wishel

论坛徽章:
0
7楼 [报告]
发表于 2010-07-15 18:07 |只看该作者
查了下，stl中的nth_element貌似满足我的需求。只是不知道性能怎样。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
peidright

论坛徽章:
0
8楼 [报告]
发表于 2010-07-15 18:10 |只看该作者
m*log(n)

最好的结果。

也就是维护一个大小为n的堆。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
bruceteen

论坛徽章:
14
巨蟹座 日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛 日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东 日期:2016-06-29 11:45:542015亚冠之全北现代 日期:2015-07-22 08:09:472015年辞旧岁徽章 日期:2015-03-03 16:54:15巨蟹座 日期:2014-12-29 08:22:29射手座 日期:2014-12-05 08:20:39狮子座 日期:2014-11-05 12:33:52寅虎 日期:2014-08-13 09:01:31巳蛇 日期:2014-06-16 16:29:52技术图书徽章 日期:2014-04-15 08:44:01天蝎座 日期:2014-03-11 13:06:45
9楼 [报告]
发表于 2010-07-15 20:37 |只看该作者
7楼说得对，应该是用nth_element，
但不知道其数据有多大？所以自己做的话，可以遍历m个数，将其中n个最大的数保存在priority_queue中
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
醉卧水云间

论坛徽章:
39
2017金鸡报晓 日期:2017-02-08 10:39:4219周年集字徽章-周 日期:2023-04-15 12:02:2715-16赛季CBA联赛之深圳 日期:2023-02-16 14:39:0220周年集字徽章-年 日期:2022-08-31 14:25:28黑曼巴 日期:2022-08-17 18:57:0919周年集字徽章-年 日期:2022-04-25 13:02:5920周年集字徽章-20 日期:2022-03-29 11:10:4620周年集字徽章-年 日期:2022-03-14 22:35:1820周年集字徽章-周 日期:2022-03-09 12:51:3220周年集字徽章-年 日期:2022-02-10 13:13:4420周年集字徽章-周 日期:2022-02-03 12:09:4420周年集字徽章-20 日期:2022-01-25 20:14:27
10楼 [报告]
发表于 2010-07-15 22:54 |只看该作者
一直用nth_element
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP