#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @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]