查找未排序數組中的所有對（x，y），以便x + y = z

我有n個數字和數字z。我想創建一個算法（僞代碼）來查找O（nlogn）中是否存在x + y = z的對（x，y）。查找未排序數組中的所有對（x，y），以便x + y = z

我認爲我可以運行quicksort算法。然後我將有2個數組：array1（元素<樞軸）和array2（元素>樞軸）。如果數組中的第一個元素是<z那麼我可以檢查array1中的所有其他元素以找到x + y = z的對。否則，如果array1中的第一個元素是> z然後我去array2並做相同的過程。我的建議是否正確？

來源

2016-11-29 Lee Yaan

當數組已經排序後，可以在O（n）中完成。 – Henry

數組未經排序。對不起，我現在編輯我的問題 –

數字是唯一的嗎？ – David

首先，排序數組。
然後設置一個指針/索引到排序數組的每一端。
如果它們總和爲z，則保留它並將兩個指針移向中間。
如果總和小於z，則將小指針移向中間。
如果總和大於z，則將大指針移向中間。
當指針滿足/通過時，就完成了。

來源

2016-11-29 15:18:05

您不需要對已排序的序列進行排序，只需搜索即可。

僞代碼：

sort(sequence) // O(NlogN) sorts are well known 
for element in sequence: // O(N) loop 
    target = z - element // constant (assuming fixed size arithmetic) 
    if target > min_element and target < max_element: // constant 
     found = binary_search(target, sequence) // O(LogN) search

複雜：O（NlogN（排序）+（N（環）* LOGN（搜索）））= O（NlogN），根據需要

來源

2016-11-29 15:18:30 Caleth

與想法數據透視不會奏效，因爲沒有好的數據透視選擇，並且因爲檢查未分類的半範圍將保持O（n）任務需要完成n/2次，因爲O（n ）。

您可以在O（n）中做到這一點，不需要通過將所有元素添加到散列表中，然後檢查每個元素x即z-x元素也存在。 x=z/2是一種特殊情況，因爲您需要驗證輸入數組中是否存在兩個z/2值。

來源

2016-11-29 15:22:19 dasblinkenlight

是的我知道我可以在O（n）中做到這一點，但我想要一個算法在O（nlogn） –

@ dimitrisdimas1313中輸入O（nlogn），然後從相反兩端搜索O（n）。整體複雜性將保持O（nlogn）。 – dasblinkenlight

這是一個很好的答案！另外，從技術上講，如果它是O（n），它也是O（nlogn）（但不是相反）。 – Lidae

查找未排序數組中的所有對（x，y），以便x + y = z

回答

相關問題