【题目描述】
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
【思路】
满足海量数据找top k,由于内存大小有限,不能一次读入海量数据。
因此建立一个大小为k的容器,不断更新此容器即可。时间复杂度为o(nlogk),遍历数组,每次遍历的时候取出容器中的最大值与遍历值对比。
【代码】
python:
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
re=[]
if len(tinput)<k or k==0:
return re
for num in tinput:
if len(re)<k:
re.append(num)
elif num<max(re):
re.remove(max(re))
re.append(num)
re.sort()
return re