發現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

發現5個元素

回答

相關問題