“在 n+2k-3 个比较中找到大小为 (2^k +1) 的数组中的第三大元素。”
这是我在算法课程期末考试中遇到的一个问题，我没有得到所有的分数。经过彻底的互联网搜索，我仍然不确定正确的答案是什么。
我意识到这是第二大问题的扩展版本，但是所要求的严格比较界限使问题变得棘手。我还找到了一个数学解释来在这里找到第 K 个元素，但是这对我来说太复杂了，我无法理解。
将数组大小表示为 n = 2^k + 1。
在考试本身中，我的答案是这样的：
我们将使用锦标赛树。首先，我们遗漏了一个任意元素。
然后构建由 2^k 个元素组成的树。因此树中有 K 个级别 (log(2^k))。
找到获胜者将需要我们进行 n-2 次比较。
在输给获胜者的人中找到最大的元素。（K-1 补偿）
在输给决赛输家的人中找到最大的元素。（K-2 补偿）
我们将比较这些和我们一开始遗漏的那个。（2个补偿）
3 个中最大的是数组中的第 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 大的广义的（K 被取了..）。
提前致谢， Itay