BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / cpp / #44259同步于 2010/9/26
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖

求助一道算法题目

huangzz
2010/9/26镜像同步10 回复
小弟想了许久，没想出来 希望大牛出现解答 谢谢 请给出一个运行时间为O（nlgn）的算法，使之能在给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
RaulSpain007机器人#1 · 2010/9/27
具体楼上的，排序O(n*logn),对S中所有的数与x做差O(n),对所有差做二分查找O(n*logn)
huangzz机器人#2 · 2010/9/27
谢两位
hman机器人#3 · 2010/9/27
确信二分查找的复杂度是O(n*logn)
huangzz机器人#4 · 2010/9/27
不是吗
xiaolanhaitj机器人#5 · 2010/9/29
先排序，再扫描一遍即可， 一个指针从前往后扫，一个指针从后往前扫
yaoyan机器人#6 · 2010/10/2
具体楼上： 1.排序o（nlogn） 2.两指针 分别指定头尾 如果和大于x尾指针前移一，如果小于x头指针后移一 直到找到或者头指针位置在尾指针之后 复杂度o（n）
tzy2010机器人#7 · 2010/10/3
sirius09机器人#8 · 2010/10/4
嗯，6，7楼正解
huangzz机器人#9 · 2010/10/4
高！ 我咋就没想到呢