algorithm - 找到任意数字数组的最大值和第 k 个最大值的最小比较次数

Question

这个问题是以下已知问题的扩展：

查找最小比较次数以找到 N 个任意数组的最大值和最小值。

事实证明，我们可以使用锦标赛树构造或使用对构造来回答它（我从这里得到了这些方法）。
我想知道以下问题的答案是什么：

找到最小比较次数，以找到 N 个任意数组的最大值和第 k 个最大值。

我不知道如何解决这个问题。我的想法是在锦标赛方法的每个级别上观察失败者/获胜者数组的一些属性，例如：如果数组是 8 6 4 3 2 1 5 7，那么每个级别的获胜者和失败者数组就像
获胜者_1 = [8, 4, 2, 7]
失败者_1 = [6, 3, 1, 5]

获胜者_获胜者_2 = [8, 7]
失败者_获胜者_2 = [4, 2]
获胜者_失败者_2 = [6, 5]
失败者_失败者_2 = [3, 1]

获胜者_获胜者_获胜者_3 = [8]
获胜者_失败者_获胜者_3 = [4]
获胜者_获胜者_失败者_3 = [6]
获胜者_失败者_失败者_3 = [3]

失败者_获胜者_获胜者_3 = [7]
失败者_失败者_获胜者_3 = [2]
失败者_获胜者_失败者_3 = [5]
失败者_失败者_失败者_3 = 1

标签： algorithmtime-complexity