题解 | #最小的K个数#

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
# 
# ** 思考：快排和快速选择到底有什么不同？
class Solution:
    def GetLeastNumbers_Solution(self , input , k ):
        # write code here
        ret = []
        n = len(input)
        if k == 0 or k > n:
            return ret
        self.qs(input, k, 0, n - 1)
        for i in range(0, k):
            ret.append(input[i])
        return ret
    
    def qs(self, arr, k, left, right):
        if left == right or left >= len(arr):
            return
        i = left
        j = right
        pivot_val = arr[left]
        while i < j:
            #右边找出第一个小于pivot_val的
            while i < j and arr[j] >= pivot_val:
                j -= 1
            #左边找出第一个大于pivot_val的
            while i < j and arr[i] <= pivot_val:
                i += 1
            self.swap(arr, i, j)
        self.swap(arr, i, left) #把left当做pivot
        #若i > k, 往i前找
        if i > k:
            self.qs(arr, k, left, i - 1)
        #若i < k, 往i后找
        if i < k:
            self.qs(arr, k, i + 1, right)
        return

    def swap(self, arr, i, j):
        tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp 
        return