算法入门---判断集合S中是否存在两个其和等于x的元素

此题是算法导论（第二版）第二章习题 2.3-7，题目如下：

请给出一个运行时间为O（n lgn）的算法，使之在给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。

思路一 ：我们最容易想到的是O（n²）的算法，大致伪码即：

1 findX(A, x){

2     for i=0 to length[A] {

3         key = A[i]

4             for j=0 to length[A]{

5                  if(j != i && key + A[j] == x ){return true}

6     }

7     return false

8 }

这里的算法不符合O(n lgn)，所以不行。

思路二：改进思路一中的算法，使第一层循环里面的4--5行的效率为 lgn。

既然4-5行的目的是找到某个符合条件的值，那么我想到了二分查找，二分查找是一个最坏O(lgn)的查找算法，但是前提是集合S有序，于是先要进行排序。伪码如下：

1 findX(A, x){

2     mergeSort(A, 0, length[A]);

3     for i=0 to length[A] {

4         key = A[i]

6         if( binarySearch(A, x-key, 0, length[A]) != i ){return true}

7     }

8     return false

9 }

第2行的归并排序运行时间为O(n lgn), 第3-7行的运行时间为O(n)*O(lgn)= O(nlgn)，故总运行时间为O(nlgn)。

思路三：继续改进思路二（感谢朱师哥）

目的是将思路二中的第6行的二分查找的次数减少。

1 将集合S排序

2 若A[0]为负数，则将集合S中的元素都加上A[0]，使集合中不存在负数。此时的x = x+A[0]

3 将集合S中比x大的元素去掉

4 在S中二分查找值近似等与x/2的元素位置，假设为m

5 遍历S，判断是否存在这样的两个元素，从m位置向两头遍历

i = m

k = m+1;

while( i>=l && k<= length[A]){

if( A[i] + A[k] == x){

return true;

}else if(A[i]+A[k] < x){

k++;

}else{

i--;

}

}

return false;

第1步为O(nlgn)，第4步为O(lgn)，第2,3,5步为O(n)，故总运行时间为O(nlgn)。

思路四：下面的算法来自算法导论的教师手册

1 将集合S排序

2 生成新的集合 S’ = {z: z = x-y} y∈S

3 将S’排序

4 使S或者S’中每个值只出现一次

5 将S和S'进行合并（Merge方法）

6 当且仅当合并后的输出序列中有相同元素，则S中存在两个元素其和等于x。

运行时间分析： 第1步和第3步均为O(n lgn)，第2,4,5,6步为O(n), 故总运行时间为O(nlgn)。

我感觉，前面三个思路都是遍历的前提下，改进基于“找”的思想，而思路四没有，想法很新颖，但是貌似空间浪费较多。大家如果有更好的思路，还请多多指教。

最后

以上就是怡然小松鼠为你收集整理的算法入门---判断集合S中是否存在两个其和等于x的元素的全部内容，希望文章能够帮你解决算法入门---判断集合S中是否存在两个其和等于x的元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。