algorithm - 在 n+2k-3 次比较中找到大小为 (2^k +1) 的数组中的第三大元素

Question

“在 n+2k-3 次比较中找到大小为 (2^k +1) 的数组中的第三大元素。”

这是我在算法类(class)期末考试中遇到的一道题，我没有得到所有的分数。经过彻底的互联网搜索后，我仍然不确定正确答案是什么。

我意识到这是第二大问题的扩展版本，但所要求的严格比较界限使问题变得棘手。我还找到了找到第 K 个元素的数学解释 here ，但是它太复杂了，我无法理解。

将数组大小表示为 n = 2^k + 1。

在考试中我的答案是这样的:

我们将使用锦标赛树。首先，我们遗漏了一个任意元素。
然后构建由 2^k 个元素组成的树。因此树中有 K 层 (log(2^k))。

找到获胜者需要我们进行 n-2 次比较。

在输给赢家的人中找出最大的元素。 (K-1 comp.)

找出输给决赛失败者的元素中最大的元素。 (K-2 comp.)

我们将比较这些和我们在开始时遗漏的那个。 (2 份)

3 中最大的是数组中的第三大。

总比较:n - 2 + k - 1 + k - 2 + 2 = n + 2k - 3。

满分 25 分，我得了 10 分。

我犯了 2 个错误。最主要的是，如果所需的元素在获胜者的子树中，我的答案将是错误的。另外，正确答案应该是我最后比较的 3 个中第二大的。

我找到的另一种算法如下:
-建立锦标赛树并找到获胜者 (n - 2)
-通过比较所有输家和赢家来找出第二大的。 (也通过锦标赛树)(k - 1)
- 答案在于最大的输家对第二大的输家，以及在第一棵树中输给决赛输家的输家。 (log(k+1) + K-1-1)

-这个解决方案假设我们遗漏的元素不是数组中最大的。如果是，我不确定它是如何工作的。另外，我可能没有正确理解比较的数量。

如果有更好解释的算法，我会很高兴。我也很想知道是否有更多通用的 L-th largest(K was taken..)。

提前致谢，伊泰

Answer 1

1. 在 n - 1 = 2^k 的元素上构造一棵锦标赛树，这些元素是任意选择的。 (n - 2 次比较)

2. 在叶子节点，用未选择的元素替换所选元素的最大值。重建锦标赛树。 (k 次比较)

3. 将丢失的元素中的最大值取为新的最大值，与第二大算法中的一样。 (k - 1 次比较)

我将把正确性证明留作练习。