通過 IT 國際公司的代碼面試，我遇到了有趣的問題。
我們需要進行多少次比較才能確定六個元素中的哪個元素是第二小或第二大的。
這六個元素都沒有相同的值。
我們有帶有六個引數的 main 函式 (v1, ..., v6)
def solve(v1, v2, v3, v4, v5, v6): # the worst case -> 9 comparisons if isLarger(v1, v2): v1, v2 = v2, v1 if isLarger(v1, v3): v1, v3 = v3, v1 if isLarger(v1, v4): v1, v4 = v4, v1 if isLarger(v1, v5): v1, v5 = v5, v1 if isLarger(v1, v6): v1, v6 = v6, v1 if isLarger(v2, v3): v2, v3 = v3, v2 if isLarger(v2, v4): v2, v4 = v4, v2 if isLarger(v2, v5): v2, v5 = v5, v2 if isLarger(v2, v6): v2, v6 = v6, v2 print(f"#comparisons = {CntComparisons}") return v2它回傳第二小的值或第二大的值。
通過比較確定該值（即它不能使用該值的索引）。
對于成對比較，我們只能使用以下函式
CntComparisons = 0 def isLarger(v1, v2): global CntComparisons CntComparisons = 1 return v1 > v2僅通過呼叫比較函式isLarger(v1, v2) 來比較值。
目標是找到一種演算法（即使在最壞的情況下）需要盡可能少的比較！
任何想法或提示如何解決這個問題？
uj5u.com熱心網友回復：
一個簡單但不是最佳的方法是使用冒泡排序的前兩次傳遞：這將交換變數對，因此將 2 個最大值冒泡到“右邊”并將它們分配給 v5 和 v6，因此 v5 將回傳為正確答案。這需要 9 次比較：第一遍 5 次，第二遍 4 次。所以我們有 9 個比較的上限。
下限是 5，因為這是找到最小值或最大值所需的比較次數，并且需要確定值是第二大或第二大。
這是一個想法：
執行 2 到 3 次比較，通過從最小到最大的交換對 v1、v2、v3 進行排序。然后我們知道 v2 既不是最小的也不是最大的。
在 v2 和最后 3 個值（v3、v4 和 v5）之間執行 3 次比較。
如果這些比較都給出相同的布爾結果，則意味著 v2 確實是答案。
如果在這些布爾結果中只有一個 True（即 v2 僅大于其中之一），則讓 vx 是 v3、v4 或 v5 中 v2 大于 vx 的一個。回傳 v1 和 vx 中的最大值：這需要另一個第7次比較。
如果在這些布爾結果中只有一個 False（即 v2 大于其中的兩個），則讓 vx 是 v3、v4 或 v5 中 v2 不大于 vx 的一個。回傳 v3 和 vx 中的最小值：這需要另一個第7次比較。
所以在最壞的情況下，我們得到了 7 次比較的結果。最好的情況需要 5 次比較（2 次用于排序步驟，c4、c5 和 c6）。
這是這個想法的一個實作：
def solve(v1, v2, v3, v4, v5, v6):
# Sort (v1, v2, v3)
if isLarger(v1, v2):
v1, v2 = v2, v1
if isLarger(v2, v3):
v2, v3 = v3, v2
if isLarger(v1, v2):
v1, v2 = v2, v1
# v2 is now certainly not the greatest nor the least
# Check how it compares with v4, v5 and v6
c4 = isLarger(v2, v4)
c5 = isLarger(v2, v5)
c6 = isLarger(v2, v6)
if c4 == c5 == c6: # All true or all false
return v2
if c4 ^ c5 ^ c6: # Only one of them is true
vx = v4 if c4 else (v5 if c5 else v6)
return v1 if isLarger(v1, vx) else vx
else: # Only one of them is false
vx = v4 if not c4 else (v5 if not c5 else v6)
return vx if isLarger(v3, vx) else v3
我在所有排列上運行了這個[1,2,3,4,5,6]，這些是結果：
- 96 次排列需要 5 次比較
- 336 個排列需要 6 個比較
- 288 個排列需要 7 個比較
平均：6.266667 次比較
uj5u.com熱心網友回復：
尋找最佳元素總是需要n-1比較。在第二個最好的元素是那些誰失去了唯一的比較中最好的。
通過安排淘汰賽，您可以保證最多log n有第二好的候選人，并在其中找到最好的進行log n比較。
因此，對于 6 個元素，您需要 5 2 = 7 次比較。
在代碼中表達這一點時，這里是第一輪消除：
if isLarger(v1, v4):
v1, v4 = v4, v1
if isLarger(v2, v5):
v2, v5 = v5, v2
if isLarger(v3, v6):
v3, v6 = v6, v3
現在接下來的兩場比賽有點棘手。您還必須交換第一輪中相應的輸家，例如
if isLarger(v2, v3):
v2, v3 = v3, v2
v5, v6 = v6, v5
保持不變式，如v2 < v5.
之后候選人是v2, v3, v4（或只是v2, v4，如果領導者v1沒有被取代）。在兩次比較中找到其中最好的。
uj5u.com熱心網友回復：
首先，如果您想從串列或陣列中找到第 k 個最大或第 k 個最小的元素，主要有兩種方法
- 天真（休閑方法）
- 巧妙的方法（現代方法）
幼稚的方法是在排序k次后每次都彈出元素。它就像，
def myfun(l):
for i in range(k):
l=sorted(l)
l.pop()
return sorted(l)[0]
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/369668.html
上一篇：影像壓縮和解壓Java