一道百度的面试题

求助一道百度的面试题


m个长度相同的降序数组，假定中间没有相同的值，求最大的前K个数

思路一：两个数组的情况下，a1[n]和a2[n]
        设有x1个前k大数在a1[n]中，x2前k大数在a2[n]中
        则x1+x2=k; x1和x2中肯定有一个大于k/2，我们只需比较a1[k/2]和a2[k/2]谁大
        我们就把它的前k/2个数取出来。剩下的递归取出。
        m个数组的情况下，我们就可以比较a[k/m]大大小，每次可以得出前k/m个数
思路二：使用归并排序
 
问下具体代码怎么实现。谢谢了。

        
        
     
[解决办法]

引用:

引用:每次分别取出每个数组中最大的，比较M次找出最大的，持续K次不就得到K个最大的值了吗？
时间复杂度O（n）空间复杂度 O（1）

我记得之前看到一个帖子好像也是 O（n）空间O（1）的，那个东西的思想是（有a[index]=value）通过一个临时变量temp与a[index]和a[value]，3者之间轮换最终排序，那个题目好像是a[n](1..n)我感觉跟你这个有点像，可以思考下。
[解决办法]
时间复杂度 O(n) 恐怕做不到,O(m*n) 倒是可以.算法如下:
STEP1: 构造序列 Z, 令它为空;
STEP2: for (i=1;i<=m;i++)
STEP3:   把 Z 与 第 i 个序列合并,送入 Z;
STEP4: 在 Z 中取前 K 个元素.
[解决办法]

输入：数组a1...am
输出：B[10]
function n_num(A,B,m)
1.C[m]={0}
2.for i=0 to 9
3.for k=0 to m
4.select max number from the 1st element of m arrays
5.B[i]=max
6.c[k]++;
7.a[k][0]=a[k][c[k]]

看行不行。
[解决办法]
归并排序+败者树.
空间O(K), 时间O(K)

查看更多 下一篇