查找數組的頂部和底部5個元素

Question

問題：

我有一個數組A，其中n≥10000個不同的正整數。試圖編寫一個算法，輸出A的一個元素x，使得x不在A的前5個元素中，也不在A的最後5個元素中.A的前5個元素和後5個元素是前5個元素， A排序後最後5個元素。另外我需要在大約50次比較中做到這一點。

我做了什麼：

我使用等級的概念，處理這個問題。 我拿6個數字並找到它的最大值。所以這將確保我的人數不在最高（前五）元素之中。但是這並不能確保我的人數不在最後5個元素之中。

僞至今：

//選擇從我的陣列A.任何6個元素

int max = A[0]; 
for(int i = 0; i<6 ; i++) 
{ 
    if(A[i] > max) 
     max = A[i]; 
} 

這會給我一個號碼（最多），這將肯定不會是數組的第一個5元之間但我應該怎麼處理最後5個元素呢？

Answer 1

我認爲你可以通過查找而不是6個元素，而是從列表中找出11個隨機元素（如果有必要，也可能不同），從而進一步改進算法。

在這個隨機的11個元素中，排序元素並選擇第6個元素。

第六元素必然是既不是前5名中也沒有底5

Answer 2

如果您不小心選擇哪一個元素（只不要被底部5和前5名），你所能做的要獲得11個第一個元素（你可以做任何事情來選擇它們，甚至是隨機選擇），對它們進行排序並採取中間的一個。

a1, a2, a3, a4, a5, Yours, a7, a8, a9, a10, a11 

即使冒泡排序你結束了（11 - 1）* 10/2 = 50的比較，但與mergesort它將方式以下。