发现5个元素

以下问题的中位数在最近的一次采访微软发现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个元素的中位数，除了快速选择

来源

2012-07-05 akash

您可能想要改善这一点的标记。有一个你可以使用的有序列表（'1.'），它们也可以嵌套。 – Flexo 2012-07-05 18:38:51

@akash：接受其他问题的答案（即，如果答案回答了您的问题，请点击'绿色选中标记'）。 – Claudiu 2012-07-05 18:42:14

@Claudiu thanx。 – akash 2012-07-05 18:43:09

Select算法将列表分成五个元素的组。（现在忽略元素被忽略。）然后，对于每个五个组，计算中位数（如果五个值可以加载到寄存器并进行比较 - 最少6个比较，则可以非常快速地进行操作）。然后在这个n/5元素的子列表上递归调用Select，以找到它们的真正中位数。

来源

2012-07-05 19:00:59 akash

我不明白“载入寄存器”是什么意思，有人可以解释吗？ – Dimath 2013-01-09 01:55:56

回答

相关问题