求一道题的算法！！ [复制链接]

电梯直达

1楼 [收藏(0)] [报告]

发表于 2008-03-19 22:15 |只看该作者 |倒序浏览

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

2楼 [报告]

发表于 2008-03-19 22:21 |只看该作者

这不就是算法导论的课后题嘛
先排序，然后二分查找。

budognai 该用户已被删除	3楼 [报告] 发表于 2008-03-21 16:50 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
budognai 该用户已被删除	实战分享：从技术角度谈机器学习入门\| 【大话IT】RadonDB低门槛向MySQL集群下战书 \| ChinaUnix打赏功能已上线！ \| 新一代分布式关系型数据库RadonDB知多少？

4楼 [报告]

发表于 2008-03-21 17:05 |只看该作者

原帖由 cugb_cat 于 2008-3-19 22:21 发表
这不就是算法导论的课后题嘛
先排序，然后二分查找。

设排序之后的数组是：{a1,a2,a3...an}
然后一次找此数组中是否含有(a1-x),(a2-x),(a3-x)...(an-x)，每次查找代价是logn，所以整体代价是nlogn