查找未排序数组中的所有对（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

回答

相关问题