|
主题 : : 腾讯的一道笔试题 ;-) [已解决] |
回复[ 8次 ]
点击[ 1808次 ] | |
|
|
|
|
|
[帖 主]
[ 发表时间：2007-12-25 18:14 ]
[引用]
[回复]
[ top ] | |
荣誉值：472
信誉值：12
注册日期：2007-10-16 15:34 |
| 在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。 | | |
|
|
|
|
|
[第1楼]
[ 回复时间：2007-12-26 12:26 ]
[引用]
[回复]
[ top ] | |
荣誉值：2
信誉值：0
注册日期：2007-12-26 11:58 |
| 将数字分为足够小的N组(内存允许的范围内)，然后分别找出这N组数中的最大数和最小数并存储，之后将N个最大数比较，N个最小数比较以确定那些组可以直接淘汰，以缩小数据的搜索范围，以此类推。之后就可以在内存充许的范围内进行数的查找！ | | |
|
|
|
|
|
[第2楼]
[ 回复时间：2008-01-02 14:12 ]
[引用]
[回复]
[ top ] | |
荣誉值：472
信誉值：12
注册日期：2007-10-16 15:34 |
|
|
|
|
|
|
[第3楼]
[ 回复时间：2008-01-05 12:38 ]
[引用]
[回复]
[ top ] | |
荣誉值：4
信誉值：10
注册日期：2007-10-08 13:17 |
| 我感觉不可，如果要找的中位数在被淘汰的一组中怎么办？岂不是结果错误 | | |
|
|
|
|
|
[第4楼]
[ 回复时间：2008-01-05 12:46 ]
[引用]
[回复]
[ top ] | |
荣誉值：4
信誉值：10
注册日期：2007-10-08 13:17 |
| 可以在1楼的方法上找出这10g个整数的最大值和最小值，然后计算出最大值和最小值的中位数是多少，然后再按1楼的方法分组(内存允许的范围内)，搜索出每组中离计算出的中位数最小的数值，然后将每组选出来的数值在组成一个组，组中的每一位和计算出来的中位数比较，取得最近的一位即可 | | |
|
|
|
|
|
[第5楼]
[ 回复时间：2008-03-13 13:40 ]
[引用]
[回复]
[ top ] | |
荣誉值：4
信誉值：0
注册日期：2008-03-12 17:27 |
| 看看这个方法是否可行: 将10G个数分为5组 每组2G个 将每组中的最大0.4G个数和最小0.4G个数取出 一共5次 然后将5次得出的最大数放一起 选取其中的最大的0.4G个数(可以保证这0.4G个数一定是整个数列中最大的0.4G个) 将其剔除 同理剔除最小的0.4G个 依次类推 直到剩余数列个数少于2G 则可直接排序得出结论 | | |
|
|
|
|
|
[第6楼]
[ 回复时间：2008-03-13 13:40 ]
[引用]
[回复]
[ top ] | |
荣誉值：4
信誉值：0
注册日期：2008-03-12 17:27 |
| 看看这个方法是否可行: 将10G个数分为5组 每组2G个 将每组中的最大0.4G个数和最小0.4G个数取出 一共5次 然后将5次得出的最大数放一起 选取其中的最大的0.4G个数(可以保证这0.4G个数一定是整个数列中最大的0.4G个) 将其剔除 同理剔除最小的0.4G个 依次类推 直到剩余数列个数少于2G 则可直接排序得出结论 | | |
|
|
|
|
|
[第7楼]
[ 回复时间：2008-03-15 17:52 ]
[引用]
[回复]
[ top ] | |
荣誉值：4
信誉值：0
注册日期：2007-08-22 13:44 |
| 你们的太麻烦了，直接用WIN32的内存映射文件技术就可以了，内存映射文件就是专门用于解决比内存大得多得多的文件的处理的。 | | |
|
|
|
|
|
[第8楼]
[ 回复时间：2008-03-28 09:25 ]
[引用]
[回复]
[ top ] | |
荣誉值：472
信誉值：12
注册日期：2007-10-16 15:34 |
| 此贴由 贴主 于 [ 2008-03-28 09:25 ] 结贴。 结贴原因：问题已解决 | | |
