最小的k个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if tinput == None or len(tinput) == 0 or k <= 0 or len(tinput) < k:
            return []
        n = len(tinput)
        start = 0
        end = n - 1
        index = self.Partition(tinput, n, start, end)
        while index != k-1:
            if index > k-1:
                end = index - 1
                index = self.Partition(tinput, n, start, end)
            else:
                start = index + 1
                index = self.Partition(tinput, n, start, end)
        output = tinput[:k]
        output.sort()
        return output




    def Partition(self, tinput, k, start, end):
        if tinput == None or len(tinput) == 0 or k <= 0 or len(tinput) < k:
            return None

        if end == start:
            return end

        pivot = tinput[start]
        leftmark = start + 1
        rightmark = end

        done = False

        while not done:
            while tinput[leftmark] <= pivot and leftmark <= rightmark:
                leftmark += 1
            while tinput[rightmark] >= pivot and rightmark >= leftmark:
                rightmark -= 1


            if leftmark > rightmark:
                return None
            else:
                tinput[leftmark], tinput[rightmark] = tinput[rightmark], tinput[leftmark]
        tinput[start], tinput[end] = tinput[end], tinput[start]
        return rightmark



    def GetLeastNumbers(self, tinput, k):
        import heapq
        if tinput == None or len(tinput) == 0 or k <= 0 or len(tinput) < k:
            return []

        output = []
        for num in tinput:
            if len(output) < k:
                output.append(num)
            else:
                output = heapq.nlargest(k, output)
                if num >= output[0]:
                    continue
                else:
                    output[0] = num

package main

import (
    "errors"
    . "../utils"
)


func Mink(nums []int, k int) ([]int, error) {
    res := []int{}

    if k > len(nums) {
        return res, errors.New("k > length of nums")
    }

    maxHeap = NewMaxHeap()


    for _, v := range nums {
        if maxHeap.length < k {
            maxHeap.Insert(v)
        } else {
            max, _ := maxHeap.Max()
            if max > v {
                maxHeap.DeleteMax()
                maxHeap.Insert(v)
            }
        }
    }

    for maxHeap.length > 0 {
        v, _ := maxHeap.DeleteMax()
        res = append(res, v)
    }

    return res, nil
}