题解 | #最小的K个数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
import heapq
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        res = []
        res1 =[]
        if len(input) < k or k == 0:
            return None
        
        for i in range(k):
            heapq.heappush(res, (-1*input[i]))
        
        for i in range(k, len(input)):
            if input[i] < (-1*res[0]):
                heapq.heapreplace(res, (-1*input[i]))

        for i in range(k):
            res1.append(-1*res[0])
            heapq.heappop(res)

        
        return res1

通过创建堆，来获取前k个小的元素。注意需要乘以-1, 比较其相反数的大小。

时间复杂度为O（NlogN），空间复杂度为O（N）。