题解 | #最小的K个数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        # 如果用大顶堆的话，建立大小为k的大顶堆，如果剩下数字里面小于顶，就把顶端挪走，替换成小的值，再堆化，最后留下的k个即为结果。
        def heapify(arr, i):
            left = 2*i + 1
            right = 2*i + 2
            pos = i
            if left < arr_len and arr[left] > arr[pos]:
                pos = left
            if right < arr_len and arr[right] > arr[pos]:
                pos = right
            if pos != i:
                arr[i], arr[pos] = arr[pos], arr[i]
                heapify(arr, pos)
        
        def build_max_heap(arr):  # 原地，所以不用返回值
            import math
            for i in range(math.floor(len(arr)/2), -1, -1):
                heapify(arr, i)
            
        if k == 0 or not input:
            return []
        temp = input[:k]
        arr_len = k
        build_max_heap(temp)
        for i in range(k, len(input)):
            if input[i] < temp[0]:
                temp[0] = input[i]
                heapify(temp, 0)
        # 时间复杂度为 O（nlogk）
        return temp