在 n+2k-3 次比较中找到大小为 (2^k +1) 的数组中的第三大元素
Finding the 3rd largest element in array of size (2^k +1) in n+2k-3 comparisons
"Find the 3rd largest element in array of size (2^k +1) in n+2k-3 comparisons."
这是我在算法课程期末考试中遇到的一道题，我没有得到所有的分数。经过彻底的互联网搜索后，我仍然不确定正确答案是什么。
我意识到这是第二大问题的扩展版本，但所要求的严格比较界限使问题变得棘手。
我还找到了一个数学解释来找到第 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。
我得到 10 分（满分 25 分）。
我犯了 2 个错误。最主要的是，如果所需的元素在获胜者的子树中，我的答案将是错误的。另外，正确答案应该是我最后比较的3个中第二大的。
我找到的另一种算法如下：
-建立锦标赛树并找到获胜者 (n - 2)
-通过比较所有输家和赢家来找出第二大的。 （也是通过锦标赛树）(k - 1)
- 答案在于最大的输家对第二大的输家，以及在第一棵树中输给决赛输家的输家。 (log(k+1) + K-1-1)
-这个解决方案假设我们遗漏的元素不是数组中最大的。如果是，我不确定它是如何工作的。
另外，我可能没有正确理解比较的数量。
我很乐意了解是否有更好解释的算法。
我也很想知道是否有更多的 L-th largest (K was taken..).
提前致谢，
伊泰
在任意选择的 n - 1 = 2k 个元素上构建锦标赛树。 （n - 2 次比较）
在叶节点处，用未被选中的元素替换被选中元素的最大值。重建锦标赛树。 (k 比较)
将丢失的元素的最大值取到新的最大值，与第二大算法中的一样。 （k - 1 次比较）
我会把正确性证明留作练习。
"Find the 3rd largest element in array of size (2^k +1) in n+2k-3 comparisons."
这是我在算法课程期末考试中遇到的一道题，我没有得到所有的分数。经过彻底的互联网搜索后，我仍然不确定正确答案是什么。
我意识到这是第二大问题的扩展版本，但所要求的严格比较界限使问题变得棘手。 我还找到了一个数学解释来找到第 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。
我得到 10 分（满分 25 分）。
我犯了 2 个错误。最主要的是，如果所需的元素在获胜者的子树中，我的答案将是错误的。另外，正确答案应该是我最后比较的3个中第二大的。
我找到的另一种算法如下：
-建立锦标赛树并找到获胜者 (n - 2)
-通过比较所有输家和赢家来找出第二大的。 （也是通过锦标赛树）(k - 1)
- 答案在于最大的输家对第二大的输家，以及在第一棵树中输给决赛输家的输家。 (log(k+1) + K-1-1)
-这个解决方案假设我们遗漏的元素不是数组中最大的。如果是，我不确定它是如何工作的。 另外，我可能没有正确理解比较的数量。
我很乐意了解是否有更好解释的算法。 我也很想知道是否有更多的 L-th largest (K was taken..).
提前致谢， 伊泰
在任意选择的 n - 1 = 2k 个元素上构建锦标赛树。 （n - 2 次比较）
在叶节点处，用未被选中的元素替换被选中元素的最大值。重建锦标赛树。 (k 比较)
将丢失的元素的最大值取到新的最大值，与第二大算法中的一样。 （k - 1 次比较）
我会把正确性证明留作练习。