题解 | #最小的K个数#

写了一个list保存前k个数,然后对输入的n-k个数中的每一个数x, 遍历k个数的数组,如果最大数比x大,那么将最大数替换为x即可,预计时间复杂度是O(kn),但是排行榜都是直接排序得到结果,这就很无语了....

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k==0:
            return []
        if len(tinput)<=k:
            return tinput
        ans = tinput[:k]
        for tmp in tinput[k:]:
            MIE = tmp+1
            ids=-1
            for idx in range(k):
                if ans[idx]>=MIE:
                    MIE,ids = ans[idx],idx
            if ids>=0:
                ans[ids]=tmp
        return ans