查找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];