在最近的微软面试中提出了以下问题
给定一个大小为 5 的未排序数组。 需要多少次最少的比较才能找到中位数?然后他将它扩展为 n 号。
根据我的 5 个元素的解是 6
1) use 3 comparisons to arrange elements in array such that a[1]<a[2] , a[4]<a[5] and a[1]<a[4]
a) compare a[1] and a[2] and swap if necessary
b) compare a[4] and a[5] and swap if necessary
c) compare a[1] and a[4].if a[4] is smaller than a[1] , then swap a[1] wid a[4] and a[2] wid a[5]
2)if a[3]>a[2].if a[2]<a[4] median value = min(a[3],a[4]) else median value=min(a[2],a[5])
3)if a[3]<a[2].if a[3]>a[4] median value = min(a[3],a[5]) else median value=min(a[2],a[4])
这可以扩展到 n 个元素吗?如果不是,除了快速选择,我们如何在 O(n) 中找到 n 个元素的中位数
最佳答案
Select 算法将列表分成五个元素一组。 (现在忽略剩余的元素。)然后,对于每组五个,计算中值(如果可以将五个值加载到寄存器中并进行比较,则该操作可能会非常快 - 最少 6 次比较)。然后在这个 n/5 元素的子列表上递归调用 Select 以找到它们的真实中位数。
关于arrays - 找到 5 个元素的中位数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11350471/