题解 | #最小的K个数#

题目：https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf 占个坑，还差一个快排的解法

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        
        
        #法二：
        #input.sort()
        #return input[:k]
        #法一：
        #return sorted(input)[:k]
        #函数sort()是对列表就地排序，不返回任何值。sorted()函数会返回一个新的排序列表

堆排序

时间复杂度：O($nlo{g}_{2}knlog\_2k$)，构建和维护大小为k的堆，需要$lo{g}_{2}klog\_2k$，加上遍历整个数组。 空间复杂度：O(k)，堆空间为k个元素。

import heapq
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        if len(input) < k:
            return input
        if k==0:
            return []
        #1、先用数组的前k个数建最大堆。python只有最小堆，没有最大堆，想要有最大堆的效果，可以将数据取相反数
        pq=[]
        n=len(input)
        for i in range(k):
            heapq.heappush(pq, -input[i])
        #2、已经变成了最小堆，找最小的k个数变成了找最大的k个数。遍历剩下来的数据，用里面大的数（大于堆顶的数）换出堆顶的数（堆顶数小）
        for i in range(k,n):
            if (-input[i])>pq[0]:
                heapq.heapreplace(pq,-input[i])
       #3、将堆顶依次弹出即是最大的k个数。再取反回来就是最小的k个数
        res=[]
        for i in range(k):
            res.append(-heapq.heappop(pq))
        return res

由于是把最大堆问题转为最小堆问题，所以最后取反回来的时候，res里面的排序是降序的。举例，按照最小堆的方式将堆顶依次弹出res为[-4,-3,-2,-1]，但是要取反，所以res会变成[4,3,2,1]。对于这道题答案也是对的，但是没升序排序，不够完善。或者可以在后面加一个res_asc.append(res.pop())，把res的元素依次从末位弹出后，添加进res_asc。

PS：python里面甚至有一个heapq.nsmallest(k,input)/heapq.nlargest(k,input)函数，直接返回数据集的最小/最大的k个数。

附一个找第K大的数的解法（top K问题）

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        pq=[]
        #1、用nums的前k个数建最小堆
        for i in range(k):
            heapq.heappush(pq,nums[i])
        #2、nums剩余的数做替换，用里面大的数换堆顶
        for i in range(k,len(nums)):
            if nums[i]>pq[0]:
                heapq.heapreplace(pq,nums[i])
        #3、堆顶的数就是第k大的数
        res=heapq.heappop(pq)
        return res