判断整数集合S是否存在有两个其和等于指定值x的元素

算法导论2.3-7：
题目就是标题，要求在nlgn内完成。从csdn上找到答案：
先排序，然后比较：

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");
nlgn+n=nlgn,即可以在规定时间内完成。

同样道理，找三个数之和也可以在n^2时间内完成。
sum=a[i]+b[i]+c[i];
等价找两个数其和为s=sum-a[i];
共有n个，每个查找为线性时间n；
nlgn+n^2=n^2。

FOJ 1707 等式数量
http://acm.fzu.edu.cn/problem.php?pid=1707

posted on 2010-05-30 22:42 CisJiong 阅读(735) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


导航

<2010年5月>
日一二三四五六
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

统计

常用链接

留言簿(2)

随笔分类(16)

随笔档案(11)

最新随笔

最新评论