首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 最近遇到一个笔试题,求高手解决! [已结贴,结贴人:nisersent]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • nisersent
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 揭贴率：
    发表于：2008-06-04 16:04:40 楼主
    问题如下：
    10亿个浮点数中，找出最大的10个浮点数，写出一个高性能算法。

    求解。
    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • velic
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 16:07:141楼 得分:0
    占个坐先
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • nisersent
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 16:28:572楼 得分:0
    帮忙解决一下,很严重的!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • norwolfli
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 17:16:563楼 得分:0
    除了循环一遍,别的想不出来.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • No_End_Point
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 17:23:234楼 得分:0
    不知道10亿个这个条件有没有暗示了什么
    循环加二分法插入
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • numen_wlm
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 17:48:365楼 得分:0
    最方便的办法：
    放进Oracle数据库里面，desc排序,取前十条记录就OK了，速度绝对最快。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jastby
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 17:50:546楼 得分:0
    引用 5 楼 numen_wlm 的回复:
    最方便的办法：
    放进Oracle数据库里面，desc排序,取前十条记录就OK了，速度绝对最快。


    把数据插进去 费时不？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • No_End_Point
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 17:56:097楼 得分:0
    晕，你插入10亿条到数据库看看！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yds204
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 18:00:168楼 得分:0
    10亿个0.0f
    不用算法
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • javabaidu
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 18:11:359楼 得分:0
    把他们排一下序，然后取前10个，或后10个
    排序算法不好写，可以看一下数据结构与算法，书上也没见有什么高效率排序算法。
    java 开发群 62873155
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ilysony
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 19:26:5210楼 得分:0
    关注
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zings
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 19:34:5411楼 得分:0
    我也不会解决，期待高手指点~~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kqw1981
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 19:41:3712楼 得分:0
    关注
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • bluesnaker
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 19:53:2513楼 得分:0
    放到list中然后用Array.sort(list)
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • numen_wlm
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 19:53:4514楼 得分:0
    引用 7 楼 No_End_Point 的回复:
    晕，你插入10亿条到数据库看看！

    怎么了，难道不能插入10亿条数据到数据库吗？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • numen_wlm
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 19:56:4415楼 得分:0
    引用 6 楼 jastby 的回复:
    引用 5 楼 numen_wlm 的回复:
    最方便的办法：
    放进Oracle数据库里面，desc排序,取前十条记录就OK了，速度绝对最快。


    把数据插进去 费时不？

    既然要用程序来做，那么可以肯定的是你肯定要首先准备10亿条数据用于读取，那么这10亿条数据准备到什么地方去？准备这10亿条数据费时不？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xwj1003
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 22:13:3116楼 得分:0
    说白了就是排序算法，难道还有比快速排序更快的排序算法吗？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jamo
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 23:19:0917楼 得分:0
    楼上对。

    或者把十亿个数逐个 alert 出来， 一直点下去， 记住哪十个最大， 哈哈哈
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • FLY_loveForever
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-04 23:58:3818楼 得分:0
    引用 11 楼 zings 的回复:
    我也不会解决，期待高手指点~~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • timsoa
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 00:23:1119楼 得分:0
    用冒泡排序！

    很烦琐，很高效！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • KK3K2005
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 00:31:2420楼 得分:1
    分段排序不知道行不行

    A.读取M*10条记录 （M>1) 排序取出最大的10条(排序算法根据每次读取的数量选择) 依大到小放进List[M*10]
    B.List放满就排序 10条最大在最前面
    C.还有记录就 继续 A 不过List开始的10条保留(从List[10]开始插入)
    D.List 开始 10条是最大的

    以上是单线程
    在List填充了开始10条后
    开M-1个线程(每个线程执行A步骤填充List[(1...M-1)*10])
    然后List排序一次
    不知道会不会快点


    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wsh19860510
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 00:41:3621楼 得分:0
    10亿个数貌似list里也放不下吧
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xiaoqingao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 01:13:0822楼 得分:0
    我觉得可以试试分组循环二分插入法  嘎嘎 
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Ren20080808
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 07:53:2123楼 得分:0
    只想到排序
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • AwL_1124
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 08:43:5424楼 得分:0
    期待解决·
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • fuyou001
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 08:50:0525楼 得分:0
    关注...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • w503426115
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 08:52:5626楼 得分:0
    引用 18 楼 FLY_loveForever 的回复:
    引用 11 楼 zings 的回复:
    我也不会解决，期待高手指点~~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Cuiyl198254
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 08:55:2827楼 得分:1
    确切的说，排序算法是不错，最好的时间复杂度是n*Log（n），对于本问题，大概需要9*10^9次比较，不过牵扯的元素移动也比较多。
    可以考虑设置1个10元素数组，用前10个值来初始化，然后挨个读取后续值，如果发现比其中的最小元素都大，那么把这个最小元素替换掉，者只需要浏览一边数据即可，时间复杂度10*10^9，这个的优点是不需要排序算法的元素移动量
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • malligator
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 08:56:2228楼 得分:0
    我觉得定义一个双向链表，遍历一遍就可以了：
    对于每一个数，按从大到小的顺序插入到链表中；若链表大小大于10，删除尾结点。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • malligator
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 09:07:2729楼 得分:0
    按从大到小的顺序插入到链表中
    －＞可优化：先拿尾结点数比较一下，若是不大于就可以PASS了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • meejoe
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 09:07:4630楼 得分:0
    外排序怎么做？关心一下
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zfl110
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-05 09:28:2431楼 得分:0
    关注
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zqrqq
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：