问题

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

解答

一般看到求最小或者最大的k个数这种题目，会想到使用堆。题目要找出最小的k个数，那么我们可以维护一个最大堆。遍历一遍数组，如果堆中数字个数还不满k个，直接将当前数字入堆。否者，将当前数字和堆顶数字比较，如果当前数字<堆顶数字，将堆顶数字移出堆，当前数字入堆。

因为python标准库只有最小堆，要特殊处理下。

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        heap = []
        for num in arr:
            if len(heap) < k:
                heapq.heappush(heap, -num)
            else:
                if -num > heap[0]:
                    heapq.heappop(heap)
                    heapq.heappush(heap, -num)
        return [-num for num in heap]