拉登o睡觉 发表于 2012-9-24 15:00:53

2013 百度校招 研发工程师 一道笔试题？？

本帖最后由 拉登o睡觉 于 2012-9-24 20:21 编辑

有20个数组，每个数组里面有500个数字，降序排列，每个数字是32位的unit,求出这10000个数字中最大的500个。
（各位各抒己见吧，尽量做到低时间复杂度，低空间复杂度,Let's go........)

空瓶氧气 发表于 2012-9-24 17:20:59

有意思，。

wangyexin 发表于 2012-9-24 17:36:38

每个数组里面有500个数组??????

拉登o睡觉 发表于 2012-9-24 20:22:22

wangyexin 发表于 2012-9-24 17:36 static/image/common/back.gif
每个数组里面有500个数组??????

哦 打错字了 我想你应该能理解吧@！

□为 发表于 2012-9-24 20:35:21

卧槽 。。 这…………2:$

wangyexin 发表于 2012-9-24 22:45:57

先给20个数组从大到小排序，然后取前面500个最大的

拉登o睡觉 发表于 2012-9-24 23:06:03

wangyexin 发表于 2012-9-24 22:45 static/image/common/back.gif
先给20个数组从大到小排序，然后取前面500个最大的

办法不错，不过还可以继续思考 其它更好一点的办法哦

asr06 发表于 2012-9-24 23:44:44

不知道这样行不行：
    定义一个数组unsigned int array(500)，用来存放最大的500个数，也要求是降序排列的。遍历给出的这20个数组时，如果遇到比array(499)大的，则把array(499)替换为改数，并进行插入排序；如果小于等于array(499)的，则停止该数组并进行下一数组的遍历。

拉登o睡觉 发表于 2012-9-25 08:12:15

asr06 发表于 2012-9-24 23:44 static/image/common/back.gif
不知道这样行不行：
    定义一个数组unsigned int array(500)，用来存放最大的500个数，也要求是降序排列 ...

我感觉行，当时 笔试时 没怎么想 就直接用的这方法，但是 应该有更厉害点的方法？？求

閑庭信步 发表于 2012-9-25 20:52:26

看 看了...........

殷大维 发表于 2012-9-25 21:04:39

安静环境符合设计的防火

闲弦 发表于 2012-9-25 22:23:18

我的想法是将原数组进行冒泡排序冒到第500个的时候将前500个输出

wangyexin 发表于 2012-9-25 22:49:02

还有一种方法就是维持一个500个元素的优先队列，插入一个删除一个

HTCUD 发表于 2012-10-7 15:47:13

将近32G的东西是不是都放在内存中？这个是关键，我感觉不能都放在内存中，按照内存的大小先从数组的倒数拿进去到内存，之后按照堆排序貌似是类似外部排序那种思想进行排序应该差不多吧。尽量少的读取外存

涅槃的龙 发表于 2012-11-7 14:55:57

首先取每个数组的第一个数字，进行对比，取出最大的。就像栈一样，取出一个数据，就让这个数组减少一个数据。然后重复这个操作500次，取出的500个数据应该是最大的前500个吧……不知能成立否

zswang 发表于 2016-8-18 18:34:30

我想到一个方法，先将20个数组的第一个数从大到小排列，然后用二分法查找后一个数在前一个数的数组中的位置并记录，就可以得到一个顺序，如果不够循环进行

游啊游 发表于 2016-8-21 22:19:14


我们首先分别给每个数组设立一个游标指向第一个数，取20个数组的第一个数据进行比较，取出这20个数里面的最大值。这20个数的最大值也就是10000个数中的最大值。然后将取出这个最大值的那个数组的游标指向下一位，然后参与下一次20个数的比较
重复这个比较500次，取出的500个数应该就是这10000个数里面的最大值……{:10_257:}
页: [1]
查看完整版本: 2013 百度校招 研发工程师 一道笔试题？？