数学研发论坛

 找回密码
 欢迎注册
查看: 4178|回复: 5

[悬赏] 寻找最大的K个数——扩展问题!

[复制链接]
发表于 2009-3-10 13:06:06 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
在面试中,有下面的问答:

问:有很多个无序的数,我们姑且假定它们各不相等,怎么选出其中最大的若干个数呢?
答:可以这样写:int array[100] ……
问:好,如果有更多的元素呢?
答:那可以改为:int array[1000] ……
问:如果我们有很多元素,例如1亿个浮点数,怎么办?
答:个,十,百,千,万……那可以写:float array [100 000 000] ……
问:这样的程序能编译运行么?
答:嗯……我从来没写过这么多的0 ……


原问题描述及解答见 http://www.msra.cn/Articles/Arti ... 1-88a1-75a4d4243f0a
pdf版本下载: 寻找最大的K个数.pdf (325.46 KB, 下载次数: 5)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-11 08:29:21 | 显示全部楼层
数组下标超过2^32次方时,32位的程序就不行了。当然可以用64位,但一般如果所用内存超过物理内存的60-70%根据系统不同,就有可能发生换页了。所以应该分步的外排序。
此时和内排序差别较大的地方在于,由于io的代价很大,所以主要问题不再是对比较次数的复杂度的细微差别,而是要尽量减小io。也就是希望可以在一次遍历完成。
但如果k足够大,一次遍历不可能完成,于是,但k相当大是就又有些像内排序了

评分

参与人数 1鲜花 +2 收起 理由
kon3155 + 2 欢迎参与!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 11:11:19 | 显示全部楼层
大家对于问题5有什么好的想法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 13:51:46 | 显示全部楼层
用类似桶排的方法,过2次应该可以吧,不行就再过几遍,内存占用也不算很大!

比如第一遍通过除以某数,将所有的数映射到一个2^16的整形范围之内,作统计,然后遍历一下这个2^16的桶,就可以算出第k个数
在哪个桶里,第2次遍历的时候,将属于这个桶里的数放到前头,并且只处理属于这个桶的数据,
把这部分数再次映射到2^16的整形范围之内,然后再求属于哪个桶,以此类推,直到这个桶里只有1个数.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 20:47:42 | 显示全部楼层
楼上回答的是哪个问题?我怎么没看明白!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 23:10:27 | 显示全部楼层
原帖由 kon3155 于 2009-3-12 20:47 发表
楼上回答的是哪个问题?我怎么没看明白!


仔细看了一下PDF,我说的大概跟解法5类似吧!不过应该可以算浮点数。
他给的方法是用位图分成2^32个桶,遍历1次,我说的是分成2^16个桶多遍历几次。可以省一些内存。另外也可以支持浮点。

另外,我的表达能力有问题,总是说不太清自己的想法!呵呵!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-6-25 16:38 , Processed in 0.357158 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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