给定n个数，如何使用最多n+log（n）比较来找到最大数和第二大数？
注意，这不是o（n+log（n）），而是真正的n+log（n）比较。
最佳答案
帕吉顿发表了评论。
让我详细说明一下。
正如pajton所说，这可以通过比赛选择来实现。
把这看作是一场淘汰赛，选手的能力有一个严格的顺序，比赛的结果完全由这个顺序决定。
在第一轮中，有一半的人被淘汰了。在下一轮的另一半等（有一些可能）。
最后，胜利者将在最后一轮决出。
这可以看作一棵树。
树的每个节点将是该节点的子节点之间匹配的获胜者。
树叶是球员。第一轮的胜者是树叶的父母等。
这是n个节点上的完整二叉树。
现在跟着赢家的路走。胜利者已经参加了N场比赛。现在想想那些log n匹配的失败者。第二个最好的肯定是最好的。
胜利者在n-1场比赛中决定（你每场淘汰一个），而在logn中胜利者在logn-1场比赛中决定。
因此，您可以确定n+logn-2比较中的最大值和第二大值。
事实上，它可以证明这是最优的。在最坏的情况下，在任何比较方案中，获胜者都必须参加logn比赛。
为了证明这一点，假设一个积分系统，在一场比赛之后，赢家得到输家的积分。一开始都是各拿一分。
最后的胜利者得了N分。
现在给定任何一个算法，它都可以被安排成让得分更多的玩家永远是赢家。因为在这种情况下，任何人的分数在任何比赛中最多都是双倍，所以在最坏的情况下，您至少需要记录胜利者玩的n场比赛。