忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 徽章 文库 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 2805 | 回复: 8

[算法] 查找最小的100个元素。 [复制链接]

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-02-17 11:20 |显示全部楼层
本帖最后由 patagonia2 于 2016-02-17 11:23 编辑

遇到这个问题。
一个没有序的数组有1000000个元素( 0 <= 整数元素 <= 100000000 )。
数组没有重复的元素。
查找最小的100个元素。


很简单,
  • 先对这个序列从小到大排序,
  • 然后输出前面的最小的100个数即可。


这样,思路很简单,整趟下来很费时。

咱们再进一步想想,是否有更好的办法。不知有没有,所以贴出来一下。


这几天,我一直在想
大神们有什么好的代码?

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-02-17 14:48 |显示全部楼层
先感谢大家,祝大家新年快乐。

论坛徽章:
0
发表于 2016-03-30 18:34 |显示全部楼层
开一个100个元素的空间,在这个空间内对所有的元素进行插入排序;如果插入不进去,那么就一定不是最小的100个。
空间复杂度O(1),时间复杂度O(n)。

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-04-10 13:12 |显示全部楼层
回复 3# jamesr


复杂

论坛徽章:
26
金牛座
日期:2014-09-15 15:59:16程序设计版块每日发帖之星
日期:2015-11-24 06:20:00程序设计版块每日发帖之星
日期:2015-11-25 06:20:0015-16赛季CBA联赛之新疆
日期:2015-12-19 19:05:48IT运维版块每日发帖之星
日期:2015-12-25 06:20:31IT运维版块每日发帖之星
日期:2015-12-25 06:20:31IT运维版块每日发帖之星
日期:2015-12-25 06:20:3315-16赛季CBA联赛之上海
日期:2016-04-15 19:51:31程序设计版块每日发帖之星
日期:2016-04-17 06:23:29程序设计版块每日发帖之星
日期:2016-04-23 06:20:00程序设计版块每日发帖之星
日期:2016-05-26 06:20:00每日论坛发贴之星
日期:2016-05-26 06:20:00
发表于 2016-04-11 11:57 |显示全部楼层
Capture.PNG

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-04-12 19:57 |显示全部楼层
回复 5# shijiang1130


照着图片上
重新敲一遍代码,有时候会偏离正确性
能贴代码吗?

论坛徽章:
26
金牛座
日期:2014-09-15 15:59:16程序设计版块每日发帖之星
日期:2015-11-24 06:20:00程序设计版块每日发帖之星
日期:2015-11-25 06:20:0015-16赛季CBA联赛之新疆
日期:2015-12-19 19:05:48IT运维版块每日发帖之星
日期:2015-12-25 06:20:31IT运维版块每日发帖之星
日期:2015-12-25 06:20:31IT运维版块每日发帖之星
日期:2015-12-25 06:20:3315-16赛季CBA联赛之上海
日期:2016-04-15 19:51:31程序设计版块每日发帖之星
日期:2016-04-17 06:23:29程序设计版块每日发帖之星
日期:2016-04-23 06:20:00程序设计版块每日发帖之星
日期:2016-05-26 06:20:00每日论坛发贴之星
日期:2016-05-26 06:20:00
发表于 2016-04-13 12:12 |显示全部楼层
回复 6# patagonia2


    不能,我故意不贴代码的

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-04-13 14:28 |显示全部楼层
回复 7# shijiang1130



重新敲一次一次的代码
虽然也不能这么说可以,但是就是这一次一次的错误,
让我深深的感觉到,其实总结归纳。
最好的是贴代码

论坛徽章:
12
射手座
日期:2014-10-02 11:31:29程序设计版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-27 06:20:00程序设计版块每日发帖之星
日期:2016-05-25 06:20:00每日论坛发贴之星
日期:2016-05-24 06:20:00程序设计版块每日发帖之星
日期:2016-05-24 06:20:0015-16赛季CBA联赛之深圳
日期:2016-05-23 15:33:59程序设计版块每日发帖之星
日期:2016-05-20 06:20:00程序设计版块每日发帖之星
日期:2016-04-26 06:20:00神斗士
日期:2015-12-03 09:27:3215-16赛季CBA联赛之八一
日期:2016-12-29 09:56:05
发表于 2016-05-25 11:49 |显示全部楼层
向上,向上
您需要登录后才可以回帖 登录 | 注册

本版积分规则

DTCC2018购票6.8折优惠进行时

中国数据库技术大会是国内数据库及大数据领域规模最大、最受欢迎的技术交流盛会。 2018年5月10-12日,第九届中国数据库技术大会将如约而至。本届大会以“数领先机•智赢未来”为主题,设定2大主会场及20个技术专场,邀请来自国内外互联网、金融、教育等行业百余位技术专家,共同探讨Oracle、MySQL、NoSQL、大数据等领域的前瞻性热点话题与技术。
----------------------------------------
优惠时间:2018年2月13日前

报名链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP