百度 客户端笔试 跪了

evaspring

我估计我得0分

_Rayx

回复 9# cjaizss


    第一二题与你想法一样。
    第三题想法有点不一样。
   
    直接归并要比较1W次。
    可以先将每个队列的第一个元素拿出来，建一个堆，每次从堆中选出一个最大的元素出来，然后看这个元素是哪个队列的，再从那个队列中再选一个最大的放到堆中，依次选出前500个即可。比较次数比直接归并要少一些。

cjaizss

_Rayx 发表于 2012-09-23 22:25
回复 9# cjaizss

我觉得在平均意义上这个算法不一定比归并强.

cjaizss

cjaizss 发表于 2012-09-23 22:50
我觉得在平均意义上这个算法不一定比归并强.

对于乱序数组取前n个其实可以做到线性,这20个桶虽然都排序了,但不一定比乱序数组有太多优势

cjaizss

_Rayx 发表于 2012-09-23 22:25
回复 9# cjaizss

我解释一下在平均意义上不一定强的原因。
“再从那个队列中再选一个最大的放到堆中”，这个可能会把非前500的数字给放进去。
可放进去的时候，你还得在算法中把它退出来，请神容易送神难啊。终究还是无法回避20个顶层之间不断的相互比较

_Rayx

回复 15# cjaizss


    对，确实是会把一些非前500的数放进去，但是最多只是20个(队列个数）非前500的数，这与你那个算法应该是一样的，归并的时候要选择一个最大的数，也必需比较所有队列的队首。
只是把查找过程由线性变成了堆。

_Rayx

回复 15# cjaizss


    在这个例子上看不到优势，毕竟20这个数太小了，如果有1万个队列，每个队例500个数，求前500，优势应该就能明显的体现出来了。

cjaizss

_Rayx 发表于 2012-09-24 08:37
回复 15# cjaizss

队列越多，越退化成无序数组。
不过我还是没有想明白你的算法，当你把一个500后的元素放进堆的时候，又是如何让其不在最后作为结果输出的呢？
我想到的一个解决方法是，有归并操作的一切比较，还加了个入堆操作，不知道你有什么好的解决手段呢。

_Rayx

回复 18# cjaizss


    是这样的：
先把每个队列的最大元素与队列号加入堆，最大的那个元素在堆顶，先取出来，然后看它是哪个队列的，再将那个队列的还未取的最大元素加入堆（O(1)即可，因为每个队列是有序的），再取最大的，依次下去。

因为在任何时候堆里只有20个元素，而且每次取的都是所有未取中的最大值，所以取500次就是前500了。

cjaizss

另外插一句，可能不见得与这个算法是一致的，对于无序数组找前n个，本来我以为入堆是最好的手段，后来我想到，这么认为可能是错的。
因为找出nth的元素就是线性算法，再比较一次输出依然是线性。（当然，这个线性如果不破坏原来数据，空间应该是O(n),空间需求较大）