如何在未排序数组中找第 K 大的元素？

直接回答：两种主流做法：1）维护一个大小为 k 的最小堆，扫完数组后堆顶即第 K 大，时间 O(n log k)、空间 O(k)；2）快速选择（QuickSelect）——借用快排的 partition，每次划分后根据枢轴下标只递归一侧，平均时间 O(n)、最坏 O(n²)，可原地进行空间 O(1)。

展开解析：QuickSelect 与快排的唯一区别是「只进一边」，平均复杂度的推导：期望每次规模减半，n + n/2 + n/4 + … = 2n。工程上必须随机选枢轴（或三数取中）避免有序输入退化成 O(n²)；极端场景还有 BFPRT（中位数的中位数）保证最坏 O(n)，但常数大、很少实际使用。选型对比是常见追问：k 很小或数据流式到达时堆更优（可增量维护、Top K 天然输出有序）；一次性静态数组且允许改动原数组时 QuickSelect 更快。另一个追问点是它与「海量数据 Top K」的衔接——单机放不下时分片 + 堆归并。

示例：

import random

def find_kth_largest(nums, k):
    target = len(nums) - k          # 第 k 大 = 升序第 len-k 小
    lo, hi = 0, len(nums) - 1
    while True:
        p = random.randint(lo, hi)
        nums[p], nums[hi] = nums[hi], nums[p]
        pivot, store = nums[hi], lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        if store == target:  return nums[store]
        if store < target:   lo = store + 1
        else:                hi = store - 1