我试图仅使用n + ceil(lg n) - 2比较来找到n个元素数组中的第二个最小元素.CLRS中的暗示说要找到最小的元素.
这需要n - 1比较,所以我留下ceil(lg n) - 1比较找到第二个最小的,一旦我知道最大的.
有任何想法吗？
谢谢,
bclayman
biz*_*lop 13
比方说,我们有一个列表1 ...一个ň用n为2的幂.
首先将元素对起来,假设1为2,a 3为4,依此类推,并将它们相互比较.这给你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).