在N个数字中找到最大和第二大

佩顿发表了评论。

让我详细说明。

正如pajton所说，这可以通过比赛选择来完成。

可以将其视为淘汰赛单打网球比赛，在此比赛中，运动员的能力具有严格的顺序，比赛结果仅由该顺序决定。

在第一轮中，有一半人被淘汰。在下一轮中，另一半等等（可能有再见）。

最终，获胜者由最后一轮决定。

可以将其视为一棵树。

树的每个节点将成为该节点的子节点之间的比赛的获胜者。

叶子是球员。第一轮的获胜者是叶子的父母等。

这是n个节点上的完整二叉树。

现在走赢家的路。获胜者参加了n场比赛。现在考虑那些log n比赛的输家。次优必须是其中最好的。

在n-1场比赛中确定获胜者（每场比赛淘汰一名），在logn中获胜者在logn -1比赛中决定。

因此，您可以在n + logn中确定最大和第二大-2个比较。

实际上，可以证明这是最佳的。在最坏情况下的任何比较方案中，获胜者都必须进行登录比赛。

为了证明这一点，我们假设一个分数系统，在比赛之后，获胜者获得了输家的分数。最初，所有起点均为1分。

最后，最终获胜者得到n分。

现在给出任何算法，都可以对其进行安排，使得分更高的玩家始终是赢家。由于在这种情况下，任何人最多在任何一场比赛中的得分都加倍，因此在最坏的情况下，您至少需要获胜者进行log
n次比赛。