查找N个号码中的最大号码和第二大号码

Question

给定n个号码，如何在最多n + log（n）个比较中找到最大号码和第二大号码？

请注意，它不是O（n + log（n）），但实际上是n + log（n）比较。

Answer 1

pajton发表了评论。

让我详细说明。

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

认为这是一场淘汰单打网球比赛，其中球员的能力有严格的顺序，比赛的结果完全由该顺序决定。

在第一轮的一半人被淘汰。在下一轮另一半等（有些可能）。

最终胜利者决定在最后一轮和最后一轮。

这可以看作是一棵树。

树的每个节点将成为该节点的子节点之间匹配的胜者。

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

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

现在按照赢家的路线。有赢家玩过的日志n比赛。现在考虑那些log n匹配的输家。第二好的必须是其中最好的。

获胜者在n-1场比赛中决定（每场比赛你击倒一场），logn中的获胜者由logn-1比赛决定。

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

事实上，它可以证明这是最佳的。在最坏的情况下，任何比较计划中，获胜者都必须进行logn比赛。

为了证明假设一个点系统，比赛结束后胜者获得输家的积分。最初，所有人都以1分开始。

最后的胜利者有n分。

现在给出了任何算法，它可以被安排，让更多点的玩家永远是赢家。由于在任何比赛中任何人的得分都至少翻番，所以在最糟糕的情况下，您至少需要获胜者出示记录n场比赛。

Answer 2

这有问题吗？这是至多3n比较（不包括i < n比较）。如果你数一数，那就是4n（或者在第二个例子中是5n）。

double first = -1e300, second = -1e300; 
for (i = 0; i < n; i++){ 
    if (a[i] > first){ 
    second = first; 
    first = a[i]; 
    } 
    else if (a[i] > second && a[i] < first){ 
    second = a[i]; 
    } 
} 

另一种方式来编写它：

for (i = 0; i < n; i++) if (a[i] > first) first = a[i]; 
for (i = 0; i < n; i++) if (a[i] < first && a[i] > second) second = a[i];