面试题40. 最小的k个数

题目

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

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

解法

借助快排的思想，index 刚好是k的时候就返回，其他情况分别处理。

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        # if k == 0:return []
        self.quickSort(arr, 0, len(arr)-1 , k)
        return arr[:k]

    def quickSort(self, array, start, end, k):
        if start >= end: return 
        index = self.partition(array, start, end)
        if index == k-1: return 
        if index > k-1 : self.quickSort(array, start, index-1, k)
        if index < k-1 : self.quickSort(array, index+1, end, k)
        
        
    def partition(self, array, start, end):
        
        pivot = array[end]
        small = start - 1
        for i in range(start, end):
            if array[i] < pivot:
                small += 1
                array[small], array[i] = array[i],array[small]
        small += 1
        array[small],array[end] = array[end],array[small]
        return small

改进
quicksort 不需要单独开一个，可以写成非递归。

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0: return []
        index = -1
        start, end = 0, len(arr)
        while index != k-1:
            index = self.partition(arr, start, end)
            if index > k-1: end = index
            if index < k-1: start = index+1
        return arr[:k]

    def partition(self, arr, start, end):
        v = arr[end-1]
        i = start - 1
        for j in range(start, end - 1):
            if arr[j] < v:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        i += 1
        arr[i], arr[end-1] = arr[end-1], arr[i]
        return i