#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        def quickSort(aList, first, last):
            if first < last:
                key = first
                left = first + 1
                right = last
                while left <= right:
                    while left <= right and aList[left] <= aList[key]:
                        left += 1
                    while left <= right and aList[key] <= aList[right]:
                        right -= 1
                    if left <= right:
                        aList[left], aList[right] = aList[right], aList[left]
                    else:
                        aList[right], aList[key] = aList[key], aList[right]
                if right > k:
                    quickSort(aList, 0, right-1)
                if right < k:
                    quickSort(aList, right+1, last)

        quickSort(input, 0, len(input) - 1)
        return input[0:k]