题目描述

最小的k个数

样例

blablabla

算法1

1.维护一个k维列表，进行插入排序
2.每次遍历到一个新的元素时，插入到列表中
3.列表长度大于k则弹出最大的一个元素

Python代码

class Solution(object):
    def getLeastNumbers_Solution(self, input, k):
        """
        :type input: list[int]
        :type k: int
        :rtype: list[int]
        """

        #插入排序
        def insert_sort(ls,num):
            n=len(ls)-1

            while n>=0:
                if ls[n]>num:
                    n-=1
                else:
                    ls.insert(n+1,num)
                    break
            if n<0:
                ls.insert(0,num)
            return ls

        ls=[]
        #遍历所有的数
        for i in input:
            if not ls:
                ls.append(i)
                continue
            ls=insert_sort(ls,i)#插入下一个元素
            #长度大于k，弹出最后一个元素
            if len(ls)>k:
                ls.pop()

        return ls