最小的 k 个数

Question

最小的 k 个数是指在一个无序数组中找出最小的 k 个数。

一种简单的方法是对数组进行排序，然后取出前 k 个数即可，时间复杂度为 O(nlogn)。

另一种更高效的方法是使用堆。可以使用一个大小为 k 的最大堆来存储当前找到的最小的 k 个数。首先将数组的前 k 个数放入堆中，然后依次遍历剩下的数，如果当前数比堆顶的数小，就将其与堆顶的数交换，并重新调整堆，确保堆内的数仍然是最小的 k 个数。遍历完成后，堆中的数即为最小的 k 个数。

下面是使用堆实现最小的 k 个数的代码：

def getLeastNumbers(arr, k):
    if not arr or k <= 0 or k > len(arr):
        return []

    # 构建最大堆
    def buildHeap(arr, k):
        for i in range(k//2-1, -1, -1):
            heapify(arr, i, k)

    # 调整堆
    def heapify(arr, i, k):
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i
        if left < k and arr[left] > arr[largest]:
            largest = left
        if right < k and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            arr[largest], arr[i] = arr[i], arr[largest]
            heapify(arr, largest, k)

    # 构建最大堆
    buildHeap(arr, k)

    # 调整堆
    for i in range(k, len(arr)):
        if arr[i] < arr[0]:
            arr[0], arr[i] = arr[i], arr[0]
            heapify(arr, 0, k)

    return arr[:k]

该方法的时间复杂度为 O(nlogk)，空间复杂度为 O(k)。