如何在不排序的情况下找出一个未排序数组的中位数？请描述算法并分析复杂度。

Question

Accepted Answer

考察点：考察经典选择算法、分区思想与复杂度分析。回答思路：明确中位数的定义（奇数/偶数长度的处理） 运用快速选择算法确定第 k 小元素 正确处理重复元素和索引边界 分析平均与最坏时间复杂度及空间复杂度

考察说明