编程之美读书笔记(寻找最大的k个数)

左手的ㄟ右手 2022-08-07 04:38 151阅读 0赞

实际的情况我觉得往往要考虑到数的范围，数的特点（整数还是浮点，重复多不多）以及K与数组长度N的比例关系，数组长度N是否超出内存大小等等因素。  
问题：有很多无序的数，姑且假定它们各不相等，怎么选出其中最大的若干个数呢？  
实际可能的应用场景  
1从1亿个qq号码中选出最值钱的5000个  
2从2亿张图片中选出点击率最高的100张  
算法一：  
直接选择排序、冒泡排序  
时间复杂度： o(N^2)  
适用条件：N不大，批量请求  
优点：简单直观，容易实现。  
缺点：对于N很大的情况，难以接受  
适用情况：N不是很大，k和N数量级接近，后续多次选择最大的K个数，有一批请求，这时可以对N个数按大小顺序进行保存。  
算法二：  
快速排序、堆排序  
时间复杂度：O(NlogN)  
适用条件：N，K较大，批量请求  
优点：N很大时最好全排序，在同等级时间复杂度中平均性能最好的全排序  
缺点：在记录有序时，快排o(N^2)  
适用情况：logN<k时，可以代替部分冒泡排序，又能达到全排序的效果  
算法三：  
部分冒泡，部分选择  
时间复杂度：O(Nk)  
适用条件;k较小(k<logN)，单个请求  
优点：简单直观，容易实现  
缺点：对于K较大的情况下，接近o(N^2)  
适用情况：K较小，比如top10等，实际实现中可能是最常用，最佳选择，单个请求，后续不必对N个数按大小顺序进行排序。  
算法四：   
类快速排序  
平均复杂度：O(NlogK)  
优点：比快速排序有较大的提升  
缺点：实现较难，最坏情况下o(NK)  
算法：假设N个数存储在s中，随机找出一个元素x，把数组分成两部分Sa和Sb，Sa中元素大于等于X，Sb中元素小于X  
分两种情况：1 Sa中元素个数小于K，Sa中所有数和Sb中最大的K-a中的元素个数  
2 Sa中元素个数大于或等于K，需要返回Sa中最大的k个元素

算法五：  
二分搜索法  
复杂度:o(Nlog(vmax-vmin)/delta)//时间复杂度跟数据分布有关  
优点：实现简单，实现性能不错  
缺点：任意两个元素的差值如果很小，性能较差  
适用情况：N很大，追求高性能  
如果全部数据不能载入内存，可以每次都遍历一遍文件，经过统计，更新解所在区间后，在遍历一次文件，把在新的区间中的元素存入新的文件，在所有元素能够全部载入内存以后，就可以不再通过读写文件的方式来操作了。  
算法：寻找K个数中最小的那一个  
两种算法:1.判断在数组中大于等于某一个数的个数是否K，二分搜索，确定这个数  
2 整数的情况下，用bit位表示，二分搜索，找寻这个数

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

1.  //二分搜索法  
2.  **int** coutnum(**int** \*list,**int** length,**int** mid)  
3.  \{  
4.      **int** num=0;  
5.      **for**(**int** j=0;j<length;j++)  
6.          **if**(list\[j\]>=mid)  
7.              num++;  
8.          **return** num;  
9.    
10. \}  
11. **void** apart(**int** \*list,**int** k,**int** length)  
12. \{  
13.     **int** vmax=100;  
14.     **int** vmin=0;  
15.     **int** vmid;  
16.     **while**((vmax-vmin)>1)  
17.     \{  
18.     vmid=vmin+(vmax-vmin)\*0.5;  
19.     **if**(coutnum(list,length,vmid)>=k)  
20.         vmin=vmid;  
21.     **else**  
22.         vmax=vmid;  
23.   
24.     \}  
25.     vmid=vmin+(vmax-vmin)\*0.5;  
26.   
27.   
28.     **int** cou=0;  
29.     **for**(**int** j=0;j<length;j++)  
30.     \{  
31.         **if**(list\[j\]>vmid)  
32.         \{  
33.             cout<<list\[j\]<<'\\n';  
34.             cou++;  
35.             **if**(cou==k)  
36.                 **break**;  
37.         \}  
38.           
39.   
40.     \}  
41.     **if**(cou<k)  
42.     \{  
43.         **while**(cou<k)  
44.         \{  
45.             cout<<vmid<<'\\n';  
46.             cou++;  
47.         \}  
48.     \}  
49.       
50.   
51.       
52. \}

算法六：  
改进堆排序  
复杂度：o(NlogK)  
优点：效率高，所需空间小，可逐个元素读入。  
缺点：无明显缺点  
适用情况：N很大，追求高性能，需要逐个读入元素  
算法描述;  
用容量为k的最小堆来存储最大的k个数，最小堆的堆顶元素就是最大的k个数中最小的一个，每次新考虑一个数x，如果x比堆顶元素小，则不改变，如果比堆顶元素大，那么用x替换堆顶元素y，替换后从新排列最小堆

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

1.  //改进堆排序  
2.  sift(**int** \*list,**int** low,**int** k)  
3.  \{  
4.      **int** p=low;  
5.      **int** q;  
6.      **while**(p<k)  
7.      \{  
8.          q=2\*p+1;  
9.          **if**(q>=k)  
10.             **break**;  
11.         **if**((q<k-1)&&(list\[q+1\]<list\[q\]))  
12.             q++;  
13.         **if**(list\[q\]<list\[p\])  
14.         \{  
15.             **int** t=list\[q\];  
16.             list\[q\]=list\[p\];  
17.             list\[p\]=t;  
18.             p=q;  
19.         \}  
20.         **else**   
21.             **break**;  
22.           
23.     \}  
24. \}  
25. **void** duitopk(**int** \*list,**int** k,**int** length)  
26. \{  
27.     **int** i;  
28.     **for**(i=k/2;i>0;i--)  
29.         sift(list,i,k);  
30.     **for**(**int** j=k;j<length;j++)  
31.     \{  
32.         **if**(list\[j\]>list\[0\])  
33.         \{  
34.             list\[0\]=list\[j\];  
35.             sift(list,0,k);  
36.         \}  
37.     \}  
38.    **for**(**int** g=0;g<k;g++)  
39.     cout<<list\[g\]<<'\\n';  
40. \}

算法七：桶排序  
复杂度：O(N)  
优点：最快方法  
缺点：有局限性，可能要通过转换  
适用情况：元素的值在给定的范围内有限个，或可分区间  
具体实现方法：  
算法描述：  
如果N个都是整数，取值范围不太大，可以考虑申请空间，记录每个整数出现的次数，然后在从大到小取出最大的k个。例如count\[i\]表示整数i在所有整数中出现的个数，只需扫描一遍就可以得到count数组，然后，寻找第k大的元素

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

1.  //桶排序  
2.  **void** topK(**int** \*list,**int** k,**int** length)  
3.  \{  
4.      **int** count\[70\]=\{0\};  
5.      **for**(**int** i=0;i<length;i++)  
6.      \{  
7.          **int** temp=list\[i\];  
8.          count\[temp\]++;  
9.      \}  
10.     **int** c=0;  
11.     **for**(**int** j=69;j>=0;j--)  
12.     \{  
13.         **if**(count\[j\]!=0)  
14.         \{  
15.             **for**(**int** g=count\[j\];g>0;g--)  
16.             \{  
17.             cout<<j<<'\\n';  
18.             c++;  
19.              **if**(c ==k)  
20.                 **break**;  
21.             \}  
22.          
23.         \}  
24.         **if**(c ==k)  
25.         **break**;    
26.     \}     
27. \}

[view plain]: http://blog.csdn.net/zyq0335/article/details/7551496#