腾讯2008年校园招聘最后一道附加题

2009-10-18 20:23:11 来自: diwayou(追求IT，成就IT)

1G可用内存，3G整型数据在硬盘上，设计算法找到中位数，大家给点思路吧，因为腾讯几乎每年最后一道都是这种类型的题

2009-10-18 20:59:43 哈哈哈 (系分+项管：扩大再生产？铁本)

这不就是个外排序吗？

> 删除
2009-10-18 21:00:33 diwayou (追求IT，成就IT)

2009-10-18 20:59:43 去死团团长 (党卫军军长)

这不就是个外排序吗？
----------------------------------------------------------------
你的意思是全部排序？

> 删除
2009-10-18 21:03:14 diwayou (追求IT，成就IT)

没有不用全部排序就能解决的方法吗？

> 删除
2009-10-18 22:00:56 Ring (第一轮结束，第二轮开始)

聪明的算法都会有预计算，排序肯定不是好办法了，中位数肯定考的是线性复杂度的算法了

> 删除
2009-10-20 09:54:41 Nate (懒得恰到好处！)

汗。这不是很容易吗？原来腾讯面试就这水准。

> 删除
2009-10-20 10:27:49 foiby (template<typename foiby>)

知道就写出来

> 删除
2009-10-20 10:34:52 ngn999 (淘宝offer到手.)

今年的差不多也是这样一道题目.
有点不一样.

> 删除
2009-10-20 18:52:46 diwayou (追求IT，成就IT)

2009-10-20 09:54:41 Nate (懒得恰到好处！) 汗。这不是很容易吗？原来腾讯面试就这水准
-------------------------------------------------------------------------------------------------
写个出来看看

> 删除
2009-10-20 18:53:14 diwayou (追求IT，成就IT)

腾讯每年都会有这种类型的题

> 删除
2009-10-20 21:51:18 酷虾 (5460（我思念你）)

我记得好像把一个数列A分成abc..........n个数列,每个数列的中位数组成的数列B的中位数和A的中位数是相等的!

> 删除
2009-10-27 08:28:56 流星

外排序的例子很多么，去看数据结构

> 删除
2009-10-29 15:20:59 LikE_DotA (圣诞归家)

大牛，就给出答案啊

> 删除
2009-11-04 21:21:10 diwayou (追求IT，成就IT)

你们的意思是排序了？有没有更有效的方法呢？

> 删除
2009-11-04 21:39:12 Ring (第一轮结束，第二轮开始)

线性算法很容易就可以想到一个啊，用线性的选择算法应该就可以吧。不过腾讯肯定考的不是这个了，因为条件里给了1G空间，就看如果通过较好的线性复杂度的预计算了，可以把那些牛书都拿出来翻一下啊。

> 删除
2009-11-04 22:03:58 diwayou (追求IT，成就IT)

内排序找中位数用的是快速选择算法，而外排序就不知道有什么好的了

> 删除
2009-11-15 14:57:05 Aston (do ur work，do not be stupid·)

Bucket sort·

> 删除
2009-12-12 20:58:47 天亮了 (恶搞的2009再见)

外排序用归并排序

> 删除
2009-12-14 15:09:52 星星

因为内存只有1G 所以定义的数组不能一次把所有数取完
所以我觉得想3G的数据分成若干等份每次取奇数个数排列去中位数
最后会有一个中位数数组再排一次求解
我觉得求中位数一定要排序吧如果有其他不要排序的方法静候达人..

> 删除