百度面试碰到一个问题

action08

有2个数组A,B 从每个数组中选择一个数相加，然后求前k个最大的数。例如 A： 3,2,1 B 4,2,3 求前2大的数是多少。结果是7和6
http://ask.chinaunix.net/question/389

windoze

想了个算法
1、在A中取top K，复杂度O(Na * log(K))
2、在B中取top K，复杂度O(Nb * log(K))
3、对于每个top K中的An，加上top K中的Bn，对结果再取top K，复杂度O(K*K)
总共的时间复杂度是O(K * log(Na) + K * log(Nb) + K*K)，如果Na和Nb近似为N，整个算法的时间复杂度约为O(N*log(K) + K*K*)，如果K相对于N很小，则第二项可以忽略
第三步还有优化的空间，不过懒得想了。

Susake_

第一个那么暴力也算最佳？？

Susake_

暂时也只能想到O(k^2)的~~

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. int comp(const void *a, const void *b)
   
6. {
   
7.         return *(int *)b - *(int *)a;
   
8. }
   
9. 
   
10. int main(int argc, char *argv[])
    
11. {
    
12.     int a[4] = {3, 2, 1}, b[4] = {4, 2, 3};
    
13.     int max[4], i, j, k;
    
14. 
    
15.     qsort(a, 3, sizeof(int), comp);
    
16.     qsort(b, 3, sizeof(int), comp);
    
17. 
    
18.     while(scanf("%d", &k) != EOF)
    
19.     {
    
20.         memset(max, 0, sizeof(max));
    
21. 
    
22.         for(i = 0; i < k; i++)
    
23.             for(j = 0; j < k; j++)
    
24.                 if(a[i] + b[j] > max[i]) max[i] = a[i] + b[j];
    
25. 
    
26.         for(i = 0; i < k; i++)
    
27.             printf("%d\n", max[i]);
    
28.     }
    
29.     return 0;
    
30. }
    

复制代码

folklore

回复 4# Susake_


    没看代码， 你这个算法复杂度里没有n,是错误的，
这种算法， 数学上能达到的理论最佳复杂度是 log n *K，
正好是建堆的算法的复杂度， 所以： 用堆算法。

timespace

这是挖坟？“CU问答”已经解决了，就是在最大堆上弹出k个元素。

Susake_

回复 5# folklore
题目本身就没有说明输入格式~~所以以提供的数据开刀了！！


   

Susake_

回复 6# timespace
百度了一下

最大堆/最小堆


　堆的定义是：n个元素的序列{k1,k2,…,kn}，当且仅当满足如下关系时被成为堆

　　 　(1)Ki <= k2i 且 ki <= k2i-1        

　　或 (2) Ki >= k2i 且 ki >= k2i-1  

　　　　　　　　　　(i = 1,2,…[n/2])

当满足(1)时，为最小堆，当满足(2)时，为最大堆。

----优先队列~~

for(i = 0; i < sizeof(a)/sizeof(int); i++)
       {
           for(j = 0;j < sizeof(b)/sizeof(int); j++)
           {
               pq.push(a+b[j]);
           }   
       }   
嗯嗯~~考虑极端情况，将n項输出~~也就是priority_queue了！！
   

xiaohuan4518

这是一个杨氏矩阵的问题，先两个数组排序，O(logn),构建矩阵时间复杂度O（N*N),根据杨氏矩阵特性，求前K个数O（N），总的时间复杂度O(N*N)

Susake_

回复 9# xiaohuan4518
是丫！！这就是我想表达的，那个第一个构建优先队列就是O(n^2)了，还不包括构建的过程~~