高效地输出无序数组中最大的 k 个元素。

Write a program that prints the k largest elements in an unordered array efficiently.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

分类: Algorithms, Data Structures

标签: K Largest Elements, Min Heap, Quickselect

目标公司: Microsoft

参考答案摘要

答案 面试中常见三种思路：①用最小堆（size=k）遍历数组，堆顶维护当前第 k 大，遇到更大元素就替换并调整，时间复杂度 O(n log k)、空间 O(k)，是最通用的解；②如果只需输出、不要求排序，最小堆即可；若要有序输出，可最后对堆元素再排序；③若允许修改数组且追求更优均摊，可用 Quickselect 找到第 k 大阈值再过滤输出，平均 O(n) 但最坏 O(n^2)。回答时说明为何选最...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。