百度 客户端笔试 跪了

_Rayx

题目还需要详细一点，如果记得的话。
坛上的也可以试试看。

_Rayx

回复 9# cjaizss


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

_Rayx

回复 15# cjaizss


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

_Rayx

回复 15# cjaizss


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

_Rayx

回复 18# cjaizss


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

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

_Rayx

回复 21# cjaizss


    最准确的说法应该是N+T-1次，N是要取的个数，T是队列个数，所以应该是进堆519次，因为我们队了选取走的500个元素要进堆，最后堆里还会剩T-1个元素。

_Rayx

回复 24# cjaizss


    对，在归并路数较多的时候才能体现出来，效率会高不少。