【剑指offer】最小的k个数 python

1,468 阅读1分钟

【题目描述】

输入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