题解 | #最小的K个数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        # 先排序然后输出前k个数


        def quick_sort(arr, left, right):
         if left < right:
            pivot_index = partition(arr, left, right)

            quick_sort(arr, left, pivot_index - 1)
            quick_sort(arr, pivot_index + 1, right)
            return arr

        def partition(arr, left, right):
            pivot = arr[left]

            while left < right:
                while left < right and arr[right] >= pivot:
                #  如果比基准值大则向前进一位，否则将值赋给左边，
                #  其实就是找到第一个小于基准值的数， 只不过判断条件反过来了
                    right -= 1
                arr[left] = arr[right]
                while left < right and arr[left] <= pivot:
                    left += 1
                arr[right] = arr[left]

            arr[left] = pivot
            return left

        lists = quick_sort(input, 0, len(input) - 1)
        new_lists = []
        for i in range(0, k):
            new_lists.append(lists[i])
        
        return new_lists