image

编辑人: 舍溪插画

calendar2025-06-12

message1

visits801

100w个数中找出最大的100个数。时间复杂度尽可能的小(附Python实现代码)

100w个数中找出最大的100个数。时间复杂度尽可能的小
方案1:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,
如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。
依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。
方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,
取前100个。复杂度为O(100w*100)。
方案3:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

代码实现如下:
import heapq #引入堆模块
import random #产生随机数
test_list = [] #测试列表
for i in range(1000000): #产生100w个数,每个数在【0,1000w】之间
test_list.append(random.random()*100000000)
heapq.nlagest(10,test_list) #求100w个数最大的10个数
heapq.nsmallest(10,test_list) #求100w个数最小的10个数

喵呜刷题:让学习像火箭一样快速,快来微信扫码,体验免费刷题服务,开启你的学习加速器!

创作类型:
原创

本文链接:100w个数中找出最大的100个数。时间复杂度尽可能的小(附Python实现代码)

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。
分享文章
share