arrays - 查找数组中第二小的元素

Question

我正在尝试仅使用 n + ceil(lg n) - 2 比较来查找 n 个元素数组中第二小的元素。 CLRS 中的提示说找到最小的元素。

这需要进行 n - 1 次比较，所以我只剩下 ceil(lg n) - 1 比较来找到第二小的，一旦我知道最大的。

有什么想法吗？

谢谢，

克莱曼

Answer 1

假设我们有一个列表 a₁...a_n，其中 n 是 2 的幂。

首先将元素配对，假设 a₁ 和 a₂，a₃ 和 ₄等等，并将它们相互比较。这为您提供了 n/2 比较。

将所有获胜者推进到下一轮，现在只有n/2个元素，并重复相同的过程。这需要 n/4 次比较。

重复上述操作，直到只剩下 1 个元素，即最终获胜者。要到达那里，您必须进行 n/2 + n/4 + ... + 1 = n-1 比较。

这很好，但第二小的是哪一个？好吧，它必须是您的获胜者在通往顶峰的过程中击败的要素之一。有 lg n 个这样的失败者，因此您需要将它们相互比较以找到最小的(需要进一步的 lg n - 1 比较)。

最小的输家是整体第二小的输家。

---

很容易证明为什么上面的方法总是找到第二小的:因为它比每个元素都小，但最终的赢家，除了与冠军的那一轮之外，它会赢得每一轮。

如果 n 不是 2 的幂，则过程几乎完全相同，除了失败者列表的长度与下一个 2 的幂次方一样长，即为什么你最终得到 ceil(lg n)。