设计一个算法，在未排序的数组中找到第 K 大的元素，要求平均时间复杂度 O(n)。

Design an algorithm to find the Kth largest element in an unsorted array with average O(n) time complexity.

题目类型: 技术面试题

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

难度: hard

标签: dropbox, generated

目标公司: Dropbox

参考答案摘要

思路分析 使用快速选择（QuickSelect）算法，基于快排分区思想。每次分区后只需处理一半数据。 参考答案 选择 pivot，分区后判断 pivot 位置与 K 的关系，递归处理对应一侧。平均 O(n)，最坏 O(n²)，可通过随机化 pivot 优化。 评分要点 理解 QuickSelect vs 完整排序的效率差异 正确实现分区逻辑 分析平均和最坏时间复杂度 了解随机化优化策略 常见追问 ...

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