回答
pajton發表了評論。
讓我詳細說明。
正如pajton所說,這可以通過錦標賽選擇來完成。
認爲這是一場淘汰單打網球比賽,其中球員的能力有嚴格的順序,比賽的結果完全由該順序決定。
在第一輪的一半人被淘汰。在下一輪另一半等(有些可能)。
最終勝利者決定在最後一輪和最後一輪。
這可以看作是一棵樹。
樹的每個節點將成爲該節點的子節點之間匹配的勝者。
葉子是球員。第一輪的獲勝者是葉子的父母等。
這是n個節點上的完整二叉樹。
現在按照贏家的路線。有贏家玩過的日誌n比賽。現在考慮那些log n匹配的輸家。第二好的必須是其中最好的。
獲勝者在n-1場比賽中決定(每場比賽你擊倒一場),logn中的獲勝者由logn-1比賽決定。
因此,您可以決定在n + logn - 2比較中的最大和第二大。
事實上,它可以證明這是最佳的。在最壞的情況下,任何比較計劃中,獲勝者都必須進行logn比賽。
爲了證明假設一個點系統,比賽結束後勝者獲得輸家的積分。最初,所有人都以1分開始。
最後的勝利者有n分。
現在給出了任何算法,它可以被安排,讓更多點的玩家永遠是贏家。由於在任何比賽中任何人的得分都至少翻番,所以在最糟糕的情況下,您至少需要獲勝者出示記錄n場比賽。
嘿,我沒有給出答案,因爲它遲到了,我要睡了:)。儘管你做得很好! – pajton 2011-04-17 13:45:04
@paj:謝謝!我只是好奇,這是我承認你首先回答它的方式:-)我會刪除那部分。 – 2011-04-17 18:06:40
這有問題嗎?這是至多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];
- 1. 查找號碼或第二大號碼
- 2. PSEUDO代碼和Python用於查找最大,第二大和最小號碼
- 3. 找到比定義的參數號碼大的最小號碼
- 4. 找到用戶輸入的最大號碼和最小號碼(方法)
- 5. 找到最大號碼。圖的邊緣
- 6. 查找n個號碼的模式
- 7. C++最大號碼驗證
- 8. 如何找到最大號碼
- 9. 查找號碼
- 10. 查找號碼括號內
- 11. 發生客戶號碼(號碼)最大的時間在表
- 12. 找到另一個號碼的號碼?
- 13. 來自大量電話號碼的電話號碼是另一個電話號碼的前置號碼?
- 14. 查找和spilit號碼
- 15. jquery查找另一個號碼的下一個/最接近的多個號碼
- 16. 最大距離的訂單號碼集
- 17. 大號碼,輸入的char []
- 18. 產生10個號碼和移動第一個號碼到最後10次
- 19. 查找公寓號碼和樓層號碼
- 20. 表格輸入號碼最大變量
- 21. Python列表大於號碼
- 22. 返回第1個最大和第2個最大號
- 23. 查找IMEI號的代碼
- 24. 查找Kaprekar的號碼
- 25. 尋找離開最小剩餘部分的最大號碼
- 26. Python的 - 檢查列表中的號碼是一個號碼
- 27. 使用grep查找其他號碼之間的特定號碼
- 28. 查找號碼cerain值
- 29. 按行查找號碼。 Javascript
- 30. ContactsContract查找電話號碼
你想實際的算法,或線索(即某種作業幫助。)? – 2011-04-17 03:08:03
我想看看實際的算法。這不是家庭作業,而是我的一位同事的問題。 – Philip 2011-04-17 03:13:16
這被稱爲錦標賽選擇算法。你可以閱讀更多的例子在這裏:http://geeksforgeeks.org/?p=11556 – pajton 2011-04-17 03:16:44