栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > Python面试题库

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

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个数

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/266577.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号