目录：LeetCode 索引

1 最小的 k 个数 面试题 17.14

设计一个算法，找出数组中最小的 k 个数。以任意顺序返回这 k 个数均可。

• 输入 arr = [1,3,5,7,2,4,6,8], k = 4 → 输出 [1,2,3,4]

思路

快速划分（Quick Select）：借鉴快速排序的 partition。时间复杂度平均 O(n)，比全局排序（O(n log n)）更优。

Python 版

class Solution: # 对数组分区，将数组最右边元素作为基准 pivot # 将小于 pivot 的元素放到左边，大于 pivot 的放到右边 def partition(self, arr: List[int], low: int, high: int): pivot = arr[high] pivot_index = low for i in range(low + 1, high + 1): if arr[i] > pivot: arr[i], arr[pivot_index] = arr[pivot_index], arr[i] pivot_index += 1 arr[high], arr[pivot_index] = arr[pivot_index], arr[high] return pivot_index def smallestK(self, arr: List[int], k: int) -> List[int]: if not isinstance(arr, list): return [] high = len(arr) - 1 if high <= k: return arr pivot_index = self.partition(arr, 0, high) while(pivot_index != k): if pivot_index > k: pivot_index = self.partition(arr[0:pivot_index], 0, pivot_index - 1) elif pivot_index < k: pivot_index += 1 return arr[0:pivot_index+1]

说明：partition 返回基准元素的最终下标；下标小于 k 说明左侧元素不够 k 个，向右边扩大；大于 k 则继续在左侧划分，直到基准下标等于 k，此时 arr[0:k] 即最小的 k 个数。