题解 | #最小的K个数#

四种解题思路 第一种：直接全排序，通过sort，切片返回最小的k个数

class Solution:
    def GetLeastNumbers_Solution(self, a, k):
         a.sort()
         return a[:k]

第二种：第一种耗时太长，简化可以为快排，找到基准数，然后判断基准点和k的大小。就不需要，全部排序。

class Solution:
    def GetLeastNumbers_Solution(self, a, k):
        def partition(a,left,right):
             key = left
             while(left<right):
                 while(left<right and a[left]<a[key]):
                     left += 1
                 while(left<right and a[right]>a[key]):
                     right -= 1
                 a[left],a[right] = a[right],a[left]
             return left
        mid = partition(a, 0, len(a)-1)
        while mid != (k-1):
             if mid >k-1:
                 mid=partition(a, 0, mid-1)
             if mid < k-1:
                 mid = partition(a, mid+1, len(a)-1)
        return a[0:k]

第三种：大数据处理思想，容器容量为k，未满直接装入，已满的话，和容器中最大的比较，替换

class Solution:
    def GetLeastNumbers_Solution(self, a, k):
         res_k = []
         for i in range(len(a)):
             if i<k:
                 res_k.append(a[i])
             else:
                 if (max(res_k)>a[i]):
                     res_k[res_k.index(max(res_k))]=a[i]
         return sorted(res_k)

第四种，构建堆,使用heapq直接返回

class Solution:
    def GetLeastNumbers_Solution(self, a, k):
         import heapq
         return heapq.nsmallest(k,a)