import heapq

def top_k_largest(nums, k):
    min_heap = []
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        elif num > min_heap[0]:
            heapq.heapreplace(min_heap, num)
    return min_heap  # 堆内元素无序，如需排序需额外操作

Top K 问题的高效解法与比较 题目描述 Top K 问题是指从一个数据集合中找出前 K 个最大或最小的元素。例如，在海量数据中找出点击量最高的前 10 篇文章，或找出工资最高的前 5 名员工。这类问题需要平衡时间复杂度和空间复杂度，尤其是在数据量无法全部装入内存时。 解题思路与步骤 1. 问题分析 Top K 问题通常分为两种类型： 找最大的 K 个元素 ：使用最小堆维护候选集，堆顶是当前 K 个元素中的最小值。 找最小的 K 个元素 ：使用最大堆维护候选集，堆顶是当前 K 个元素中的最大值。 核心挑战是如何避免对所有数据排序（O(n log n)），将复杂度优化到 O(n log K)。 2. 解法一：快速选择算法（QuickSelect） 适用场景 ：数据可全部存入内存，且不需要实时更新。 步骤 ： 基于快速排序的划分（Partition）操作，随机选一个基准值（pivot）。 将数组划分为两部分，左侧元素 ≥ pivot（找最大 K 个时），右侧元素 < pivot。 判断基准值的位置与 K 的关系： 若基准值位置 = K-1，则左侧的 K 个元素即为答案。 若位置 > K-1，在左半部分递归查找。 若位置 < K-1，在右半部分递归查找。 时间复杂度 ：平均 O(n)，最坏 O(n²)（可通过随机化避免）。 缺点 ：需要修改原数组，且不适合数据流场景。 3. 解法二：堆（Heap）法 适用场景 ：数据流或动态数据，只需单次扫描。 步骤（以找最大 K 个为例） ： 初始化一个大小为 K 的最小堆。 遍历数据： 若堆中元素不足 K 个，直接插入。 若堆已满，比较新元素与堆顶： 若新元素 > 堆顶，弹出堆顶并插入新元素。 遍历完成后，堆中即为最大的 K 个元素。 时间复杂度 ：O(n log K)。 空间复杂度 ：O(K)。 示例代码（Python） 4. 解法三：二叉搜索树（BST）或平衡树 适用场景 ：需要动态插入和删除，且支持按排名查询。 步骤 ： 用平衡树（如红黑树）维护数据，每个节点记录子树大小。 插入/删除操作维护树的结构和大小信息。 通过排名直接获取第 K 大或第 K 小的元素。 时间复杂度 ：O(n log n) 构建，O(log n) 动态操作。 缺点 ：实现复杂，通常使用语言内置库（如 C++ 的 std::multiset ）。 5. 解法四：桶排序（Bucket Sort） 适用场景 ：数据范围有限（如年龄、分数）。 步骤 ： 统计每个值出现的频率。 从最高/最低值的桶开始收集元素，直到凑满 K 个。 时间复杂度 ：O(n + m)，m 为数据范围。 6. 解法五：海量数据下的外部排序优化 适用场景 ：数据无法全部装入内存。 步骤 ： 将数据分割成多个小块，每个块在内存中排序并保存到文件。 使用多路归并排序，维护一个大小为 K 的堆，每次从各块读取当前最大值，合并结果。 7. 解法比较总结 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |--------------|------------------|------------|-----------------------------| | 快速选择 | 平均 O(n) | O(1) | 静态数据，允许修改原数组 | | 堆 | O(n log K) | O(K) | 数据流或动态数据 | | 平衡树 | O(n log n) | O(n) | 需要动态操作和排名查询 | | 桶排序 | O(n + m) | O(m) | 数据范围有限 | | 外部排序优化 | O(n log n) | O(K) | 海量数据，无法全部装入内存 | 关键点 数据是否可全部放入内存？ 数据是静态还是动态（数据流）？ 是否需要频繁更新或查询？ 时间复杂度与空间复杂度的权衡。 通过以上分析，可根据具体场景选择最合适的解法。