找到5个元素的中位数
在最近的一次微软访谈中提出了以下问题
给定一个大小为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，以找到它们的真正中位数。
链接地址: http://www.djcxy.com/p/61253.html