算法導論算法

Question

的類型，我學習算法，我讀的書「算法導論第3版」，並在問題部分它描述了下一個問題：

描述一個O（N * log（n）） - 時間算法，給定一個n個整數S和另一個整數x，確定S中是否存在兩個元素，其和爲x。

我不知道它是否提出並命令Set或無序集？

Answer 1

讓x是你想要的總和。首先對數組進行排序。然後對數組中的每個元素（a [i]），使用二分搜索來查找數組中是否存在（x-a [i]）。

的僞代碼：

sort(a,n) 
for i : 1 to n 
    if(binary_search(a,i+1,n-1,x-a[i])) 
      return true 
return false 

其他方法： 排序後，第一個和最後使用兩個指針來檢查：

while(first < last) { 
     if(a[first]+a[last] == x) return true; 
     else if(a[first]+a[last] < x) first++; 
     else if(a[first]+a[last] > x) last--; 
    } 
    return false; 

Answer 2

給定一個有序數組，你可以找到，如果有一對與O（n）算術運算相加得到x。

i := 0 
j := len(A) - 1 
while i < j { 
    if A[i] + A[j] < x { 
     i += 1 
    } else if A[i] + A[j] == x { 
     return true 
    } else if A[i] + A[j] > x { 
     j -= 1 
    } 
} 
return false 

鑑於此，就可以判斷是否有任何陣列包含一對元件，總結於x使用了O通過排序數組，然後使用上面的算法（N log n）的算術運算。