在n + 2k-3比較中找出大小爲（2^k +1）的第三大元素

Question

「在n + 2k-3個比較中查找大小爲（2^k + 1）的第三大元素「。

這是一個我在算法課程期末考試中遇到的問題，我沒有得到所有要點。我不知道徹底的互聯網搜索後，什麼是正確的答案。

我意識到這是第二大問題的擴展版本，但所要求的嚴格比較界限使問題變得棘手。 我也找到了一個數學解釋來找到第K個元素here，但是這對我來說太複雜了。

表示數組大小爲n = 2^K + 1

在考試本身我的回答是這樣的：

我們將使用一個比賽樹。首先，我們排除了任意的因素。
然後建立由2^k個元素組成的樹。因此樹中有K個級別（log（2^k））。

找到勝利者將帶我們進行n-2次比較。

尋找失敗者中最大的元素。 （K-1 comp。）

找到輸給決賽輸家的人中最大的一個。 （K-2 comp。）

我們將比較這些和我們在開始時忽略的一個。 （2 comp。）

3中最大的一個是陣列中的第3大。

總的比較：N - 2 + K - 1 + K - 2 + 2 = N + 2K - 3

我得到了10分滿分的25

我已經做了2次失誤。主要的是如果期望的元素在贏家的子樹中，我的回答將是不正確的。此外，正確的答案應該是我最後比較的3我中的第二大。

另一種算法，我發現如下：
- 建材錦標賽樹和尋找贏家（N - 2）
所有失敗者比較的贏家-Finding第二位。 （也可以通過錦標賽樹）（k - 1）
- 答案在最大的輸家中排名第二，輸家在第一棵樹中輸了。 （log（k + 1）+ K-1-1）

- 此解決方案假定我們省略的元素不是數組中最大的元素。如果是這樣，我不確定它的行爲。 另外，我可能沒有正確理解比較的數量。

我很樂意看看是否有更好的解釋算法。 我也很想知道是否有更多的第L個最大（K被採取..）。

由於提前， 伊泰

Answer 1

1. 構造n個比賽樹 - 1 = 2 ^{k中的元素的}，任意選擇。 （n - 2比較）

2. 在葉子處，用未選擇的元素替換所選元素的最大值。重建錦標賽樹。 （k次比較）

3. 取最大值丟失到新的最大值，如第二大算法。 （k - 1比較）

我會留下正確性證明作爲練習。