题解 | #最小的K个数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
import heapq
class Solution:
    # def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
    #     """
    #     method_1: 
    #     思路： 
    #     step1: 列表排序
    #     step2: 按照k值输出列表指定长度的子列表
    #     """
    #     # write code here
    #     # rst = list()
    #     if len(input)== 0 or k == 0:
    #         return []
    #     input.sort()
    #     # print("input: ", input)
    #     print("rst: ", input[:4])
    #     return input[:k]

    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        """
        method_2: 堆排序， 有限队列。
        优先队列 PriorityQueue， 是一种内置的基于堆排序的容器，氛围大定堆 和小顶堆， 大顶堆的堆定为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。

        思路： 
        step1: 利用 input数组中的前k个元素，构建一个大小为k的大顶堆，堆顶为这k个元素的最大值。
        step2: 对于后续的元素，一次比较其与堆顶的大小，若是比堆顶小，则堆顶弹出，再将新数加入堆中， 直至数组结束，保证堆中的k个最小。
        step3: 最后将堆顶依次弹出即是最小的k个数。
        """
        rst = list()
        if len(input) >= k and k != 0:
            pq = list()
            # 小顶堆， 每次都要乘-1？
            for i in range(k):
                heapq.heappush(pq, (-1 * input[i]))
            for i in range(k, len(input)):
                # 较小元素入堆
                if (-1 * pq[0]) > input[i]:
                    heapq.heapreplace(pq, (-1 * input[i]))

            # 堆中元素取出入数组
            for i in range(k):
                rst.append(-1 * pq[0])
                heapq.heappop(pq)

        return rst[::-1]
        pass
		
		核心是： 先排序，之后输出，如果吧排序做好，后续的输出就不成问题。