从100万个数中找出最大的前100个数

谁践踏了优雅 2022-05-10 23:46 194阅读 0赞

[https://blog.csdn.net/cslbupt/article/details/65935577][https_blog.csdn.net_cslbupt_article_details_65935577]

1.算法如下：根据快速排序划分的思想  
(1) 递归对所有数据分成\[a,b）b（b,d\]两个区间，(b,d\]区间内的数都是大于\[a,b)区间内的数  
(2) 对(b,d\]重复(1)操作，直到最右边的区间个数小于100个。注意\[a,b)区间不用划分  
(3) 返回上一个区间，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为\[a2,b2）b2（b2,d2\]两个区间，取（b2,d2\]区间。如果个数不够，继续(3)操作，如果个数超过100的就重复1操作，直到最后右边只有100个数为止。

2.先取出前100个数，维护一个100个数的最小堆，遍历一遍剩余的元素，在此过程中维护堆就可以了。具体步骤如下：  
step1：取前m个元素（例如m=100），建立一个小顶堆。保持一个小顶堆得性质的步骤，运行时间为O（lgm);建立一个小顶堆运行时间为m\*O（lgm）=O(m lgm);  
step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素小，直接丢弃  
如果大于堆顶元素，则用该元素替换堆顶元素，然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素，因此需要维护堆的代价为(N-m)\*O(lgm);  
最后这个堆中的元素就是前最大的10W个。时间复杂度为O(N lgm）。

补充：这个方法的说法也可以更简化一些：  
假设数组arr保存100个数字，首先取前100个数字放入数组arr，对于第101个数字k，如果k大于arr中的最小数，则用k替换最小数，对剩下的数字都进行这种处理。

3.分块查找  
先把100w个数分成100份，每份1w个数。先分别找出每1w个数里面的最大的数，然后比较。找出100个最大的数中的最大的数和最小的数，取最大数的这组的第二大的数，与最小的数比较。。。。

[https_blog.csdn.net_cslbupt_article_details_65935577]: https://blog.csdn.net/cslbupt/article/details/65935577