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