最小K个数

本题解采用了快速选择算法来找到数组中最小的k个数。快速选择是快速排序算法的变形，主要用于在未完全排序的数组中找到第k小的元素。算法首先选择一个随机的枢轴元素，然后将数组分为小于枢轴和大于枢轴的两部分，类似于快速排序。根据枢轴的位置与k的关系，决定是继续在左侧还是右侧递归查找。如果枢轴位置正好是k，那么左侧的元素就是所需的最小的k个数。

时间复杂度: O(n)

空间复杂度: O(log n)

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []  # 如果k为0，直接返回空列表
        self.random_select(arr, 0, len(arr) - 1, k)  # 调用递归函数进行快速选择
        return arr[:k]  # 返回前k个元素
    
    def random_select(self, arr, left, right, k):
        pivotIndex = self.partition(arr, left, right)  # 进行一次划分
        nums = pivotIndex - left + 1  # 计算枢轴左侧的元素数量
        if k < nums:
            self.random_select(arr, left, pivotIndex - 1, k)  # 如果k小于枢轴左侧的数量，递归在左侧继续查找
        elif k > nums:
            self.random_select(arr, pivotIndex + 1, right, k - nums)  # 如果k大于枢轴左侧的数量加1，递归在右侧查找

    def partition(self, nums, left, right):
        import random
        p = random.randint(left, right)  # 随机选择一个枢轴
        nums[left], nums[p] = nums[p], nums[left]  # 将枢轴交换到最左侧
        le = left + 1
        ge = right
        pivot = nums[left]  # 枢轴的值

        while True:
            while le <= ge and nums[le] < pivot:
                le += 1  # 移动左指针
            while le <= ge and nums[ge] > pivot:
                ge -= 1  # 移动右指针
            if le >= ge:
                break  # 指针相遇，停止循环
            nums[le], nums[ge] = nums[ge], nums[le]  # 交换左右指针的元素
            le += 1
            ge -= 1
        nums[left], nums[ge] = nums[ge], nums[left]  # 将枢轴交换到最终位置
        return ge  # 返回枢轴的最终位置