求助一道时间复杂度为nlgn的算法题
请给出一个运行时间为o(nlgn)的算法，使之能在给定一个由n个整数构成的集合s和另一个整数x时，判断出s中是否存在有两个其和等于x的元素。
[解决办法]
简单点的办法是对集合排序+二分查找。
[解决办法]
先对集合排序，假设按照大小顺序的编号分别为0到n-1;
然后当前最大跟最小元素的和跟x进行比较；
int i=0,j=n-1;
int b=0;
while (i<j)
{
int k=s[i]+s[j];
if (k==x) b=1,break;
else if (k<x) i++;
else j--;
}
if (b) printf("Y\n");
else printf("N\n");
[解决办法]
1.Y={y|y=x-s[i]},Y的大小为n,对集合Y进行排序,去掉重复数,得到集合Z-------(去掉重复数)
2.合并集合Z和S,得到一个结合A,A的大小为:<=2n;
对A进行排序,排好序后遍历集合,可以知道有没有重复数,如果有的话就说明存在有两个其和等于x的元素;(寻找重复数)
复杂度:n+nlgn+n+2nlg2n+2n O(nlgn)
对于上面的"去掉重复数"和"寻找重复数"步骤可以用其它方法实现,不一定用排序的方法
[解决办法]
的确
改进如下：
1.将集合S划分成两个集合{A|小于X/2}和{B|大于X/2并且小于X}
2.Y={y ¦y=B[i]-X/2},然后在A和Y之间找是否有相同的数
这样算法还是一样，但是大小为n
[解决办法]
#include <vector>
#inlcude <algorithm>
using std::vector;
using std::sort;
bool Look_Element(vector<int>&a, int Element)
{
sort(a.begin(), a.end());
return search(a, Element);
}
bool search(vector<int>& b, int c)
{
for(vector<int>::iterator itt = b.begin(); itt != b.end(); ++itt)
{
int a = c- *itt;
vector<int>::iterator it = find(b.begin(), b.end(), a );
if(it != b.end())
return true;
else
return fase;
}
}
