【编程之美】读书笔记：寻找最大的K个数

╰+哭是因爲堅強的太久メ 2022-07-17 04:08 177阅读 0赞

**问题：**查找大量无序元素中最大的K个数。

**解法一：**该解法是大部分能想到的，也是第一想到的方法。假设数据量不大，可以先用快速排序或堆排序，他们的平均时间复杂度为O(N\*logN),然后取出前K个，时间复杂度为O(K)，总的时间复杂度为O(N\*logN)+O(K).  
        当K=1时，上面的算法的时间复杂度也是O(N\*logN)，上面的算法是把整个数组都进行了排序，而原题目只要求最大的K个数，并不需要前K个数有限，也不需要后N-K个数有序。可以通过部分排序算法如选择排序和交换排序，把N个数中的前K个数排序出来，复杂度为O(N\*K),选择哪一个，取决于K的大小，在K(K<logN)较小的情况下，选择部分排序。

**解法二：(掌握)**避免对前K个数进行排序来获取更好的性能(利用快速排序的原理)。  
        假设N个数存储在数组S中，从数组中随机找一个元素X，将数组分成两部分Sa和Sb.Sa中的元素大于等于X,Sb中的元素小于X。  
    出现如下两种情况：  
   **(1)若Sa组的个数大于或等于K，则继续在sa分组中找取最大的K个数字 。**  
   **(2)若Sa组中的数字小于K ，其个数为T，则继续在sb中找取 K-T个数字 。**  
   一直这样递归下去，不断把问题分解成小问题，平均时间复杂度为O(N\*logK)。  
   代码如下：

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  /\*将数组a\[s\]...a\[t\]中的元素用一个元素划开，保存中a\[k\]中\*/  
2.  **void** partition(**int** a\[\], **int** s,**int** t,**int** &k)    
3.  \{    
4.      **int** i,j,x;    
5.      x=a\[s\];    //取划分元素     
6.      i=s;        //扫描指针初值     
7.      j=t;    
8.      **do**    
9.      \{    
10.         **while**((a\[j\]<x)&&i<j) j--;   //从右向左扫描,如果是比划分元素小，则不动  
11.         **if**(i<j) a\[i++\]=a\[j\];           //大元素向左边移     
12.         **while**((a\[i\]>=x)&&i<j) i++;      //从左向右扫描，如果是比划分元素大，则不动   
13.         **if**(i<j) a\[j--\]=a\[i\];            //小元素向右边移     
14.     
15.     \}**while**(i<j); //直到指针i与j相等      
16. a\[i\]=x;      //划分元素就位     
17. k=i;    
18. \}    
19. /\*查找数组前K个最大的元素，index:返回数组中最大元素中第K个元素的下标(从0开始编号),high为数组最大下标\*/  
20. **int** FindKMax(**int** a\[\],**int** low,**int** high,**int** k)  
21. \{   
22.      **int** q;  
23. **int** index=-1;  
24.    **if**(low < high)    
25.       \{    
26.         partition(a , low , high,q);    
27.         **int** len = q - low + 1; //表示第几个位置      
28.         **if**(len == k)    
29.          index=q; //返回第k个位置     
30.         **else** **if**(len < k)     
31.          index= FindKMax(a , q + 1 , high , k-len);       
32.        **else**   
33.         index=FindKMax(a , low , q - 1, k);    
34.       \}    
35.     **return** index;  
36.   
37. \}  
38. **int** main()  
39. \{  
40.      **int** a\[\]=\{20,100,4,2,87,9,8,5,46,26\};    
41.     **int** Len=**sizeof**(a)/**sizeof**(**int**);   
42.      **int** K=4;  
43.  FindKMax(a , 0 , Len- 1 , K) ;      
44.     **for**(**int** i = 0 ; i < K ; i++)    
45.       cout<<a\[i\]<<" ";    
46.  **return** 0;  
47. \}

** 解法三:(掌握)**用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆。如果X比堆顶元素大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。 全部的时间复杂度为O(N\*logK)。  
          这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次，第一种方法则会多次遍历数组。 如果所查找的K的数量比较大。可以考虑先求出k\` ，然后再求出看k\`+1 到 2 \* k\`之间的数据，然后一次求取。  
    
  代码如下：

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  **void** heapifymin(**int** Array\[\],**int** i,**int** size)  
2.   \{  
3.      **if**(i<size)  
4.   \{  
5.    **int** left=2\*i+1;  
6.    **int** right=2\*i+2;  
7.    **int** smallest=i;//假设最小的节点为父结点  
8.    //确定三个结点中的最大结点  
9.    **if**(left<size)  
10.   \{  
11.    **if**(Array\[smallest\]>Array\[left\])  
12.     smallest=left;  
13.   \}  
14.   **if**(right<size)  
15.   \{  
16.           **if**(Array\[smallest\]>Array\[right\])  
17.     smallest=right;  
18.   \}  
19.   
20.   //开始交换父结点和最大的子结点  
21.        **if**(smallest!=i)  
22.     \{  
23.      **int** temp=Array\[smallest\];  
24.      Array\[smallest\]=Array\[i\];  
25.      Array\[i\]=temp;  
26.      heapifymin(Array,smallest,size);//对调整的结点做同样的交换  
27.     \}  
28.  \}  
29.  \}  
30.   
31. //建堆过程，建立最小堆,从最后一个结点开始调整为最小堆  
32. **void** min\_heapify(**int** Array\[\],**int** size)  
33.  \{  
34.   **int** i;  
35.   **for**(i=size-1;i>=0;i--)  
36.    heapifymin(Array,i,size);  
37.     
38.  \}  
39.  //k为需要查找的最大元素个数，size为数组大小，kMax存储k个元素的最小堆  
40. **void** FindMax(**int** Array\[\],**int** k,**int** size,**int** kMax\[\])  
41. \{  
42.   
43.   **for**(**int** i=0;i<k;i++)  
44.    kMax\[i\]=Array\[i\];  
45.  //对kMax中的元素建立最小堆  
46.    min\_heapify(kMax,k);  
47.  printf("最小堆如下所示 : \\n");  
48. **for**(i=0;i<k;i++)  
49. printf("%4d",kMax\[i\]);  
50. printf("\\n");  
51.   
52.  **for**(**int** j=k;j<size;j++)  
53.   \{  
54.      **if**(Array\[j\]>kMax\[0\]) //如果最小堆的堆顶元素，替换  
55.   \{  
56.         **int** temp=kMax\[0\];  
57.   kMax\[0\]=Array\[j\];  
58.      Array\[j\]=temp;  
59.   //可能破坏堆结构，调整kMax堆  
60.   min\_heapify(kMax,k);  
61.   \}  
62.     
63.   
64.   \}  
65.   
66.   
67.    
68. \}  
69.   
70. **int** main()  
71. \{  
72.       
73.  **int** a\[\]=\{10,23,8,2,52,35,7,1,12\};  
74.  **int** length=**sizeof**(a)/**sizeof**(**int**);  
75.   
76.     //最大四个元素为23,52,35,12  
77. /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*查找数组中前K个最大的元素\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
78.  **int** k=4;  
79.  **int** \* kMax=(**int** \*)malloc(k\***sizeof**(**int**));  
80.  FindMax(a,k,length,kMax);  
81.   
82.    printf("最大的%d个元素如下所示 : \\n",k);  
83.     **for**(**int** i=0;i<k;i++)  
84.         printf("%4d",kMax\[i\]);  
85.  printf("\\n");  
86.  **return** 0;  
87. \}

** 解法四：**这也是寻找Ｎ个数中的第Ｋ大的数算法。利用二分的方法求取TOP k问题。 首先查找 max 和 min，然后计算出mid = (max + min) / 2该算法的实质是寻找最大的K个数中最小的一个。

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  **const** **int** N = 8 ;    
2.   **const** **int** K = 4 ;    
3.       
4.   /\*  
5.   利用二分的方法求取TOP k问题。  
6.   首先查找 max 和 min，然后计算出 mid = (max + min) / 2  
7.   该算法的实质是寻找最大的K个数中最小的一个。   
8.     
9.     
10.  \*/    
11.      
12.  **int** find(**int** \* a , **int** x) //查询出大于或者等于x的元素个数      
13.  \{    
14.      **int** sum = 0 ;    
15.          
16.      **for**(**int** i = 0 ; i < N ; i++ )    
17.      \{     
18.         **if**(a\[i\] >= x)    
19.           sum++ ;                    
20.      \}    
21.       **return** sum ;    
22.  \}    
23.      
24.    
25.  **int** getK(**int** \* a , **int** max , **int** min) //最终max min之间只会存在一个或者多个相同的数字      
26.  \{    
27.      **while**(max - min > 1)             //max - min的值应该保证比两个最小的元素之差要小      
28.       \{    
29.         **int** mid = (max + min) / 2 ;    
30.         **int** num = find(a , mid) ;    //返回比mid大的数字个数      
31.         **if**(num >= K)                 //最大的k个数目都要比min值大      
32.            min = mid ;                   
33.         **else**    
34.            max = mid  ;    
35.       \}    
36.       cout<<"end"<<endl;    
37.       **return** min ;    
38.  \}    
39.      
40.  **int** main()    
41.  \{    
42.    **int** a\[N\] = \{54, 2 ,5 ,11 ,554 ,65 ,33 ,2\} ;      
43.    **int** x = getK(a , 554 , 2) ;     
44.    cout<<x<<endl ;     
45.    getchar() ;     
46.    **return** 0 ;        
47.  \}

该算法在实际应用中效果不佳。

**          解法五：**如果N个数都是正数，取值范围不太大，可以考虑用空间换时间。申请一个包括N中最大值的MAXN大小的数组count\[MAXN\]，count\[i\]表示整数i在所有整数中的个数。这样只要扫描一遍数组，就可以得到第K大的元素。  
代码如下：

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  **for**(sumCount = 0, v = MAXN -1; v >=0; v--)    
2.  \{    
3.         cumCount += count\[v\];    
4.         **if**(sumCount >= k)    
5.              **break**;    
6.  \}    
7.  **return** v;

**        扩展问题：**  
1.如果需要找出N个数中最大的K个不同的浮点数呢？比如，含有10个浮点数的数组（1.5，1.5，2.5，3.5，3.5，5，0，- 1.5，3.5）中最大的3个不同的浮点数是（5，3.5，2.5）。  
     解答：除了**解法五**不行，其他的都可以。因为最后一种需要是正数。  
2. 如果是找第k到第m（0<k<=m<=n)大的数呢？  
       解答：可以用小根堆来先求出m个最大的，然后从中输出k到m个。  
3. 在搜索引擎中，网络上的每个网页都有“权威性”权重，如page rank。如果我们需要寻找权重最大的K个网页，而网页的权重会不断地更新，那么算法要如何变动以达到快速更新（incremental update）并及时返回权重最大的K个网页？  
   解答：(**解法三**)用堆排序当每一个网页权重更新的时候，更新堆。

**举一反三：**查找最小的K个元素

解答：最直观的方法是用快速排序或堆排序先排好，在取前K小的数据。最好的办法是利用**解法二**和**解法三**的原理进行查找。

[view plain]: http://blog.csdn.net/xiaoding133/article/details/8037086#