题解 | #最小的K个数#
最小的K个数
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @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)。