那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

(算法导论习题解exercise2.3-7)给定一个整数序列以及一个数X,确定该序列中是否有两个数的和为X

这是<<算法导论>>中的一题,exercise 2.3-7.

可以这么做:
1) 首先将序列排序,去掉重复的元素.
2) 其次生成一个序列, 该序列中每个元素都是X-原序列中的值, 同样的,去重.
3) 对这两个已经排序好的序列进行合并操作.
4) 如果有两个元素之和为X, 那么在合并的时候必然是相邻的元素.

比如序列 1, 3, 5, 8, X=8, 生成的新序列排序之后就是0, 3, 5, 7.在合并操作时出现两个相邻的3,因此该序列中存在3和5之和为8.

我想的另一种做法:
遍历序列, 每次遍历时将X-序列元素的差放入到另一个新的序列中的合适位置去, 使这个新的序列一直都是有序的.同样的, 每次遍历的时候都在这个新的序列中搜索是否存在当前元素, 由于是有序的, 所以可以采用二分查找的方法.
比如对于序列5,1,8,3, X=8.
首先遍历的元素是5, 此时新的序列是空的,将8-5=3放入到新的序列中.
其次遍历的元素是1, 此时新的序列只有元素3, 将8-1=7放入到新的序列中, 形成3,7的有序序列.
再次遍历的元素是8, 此时新的序列为3,7, 将8-8=0放入到新的序列中, 形成0,3,7的有序序列.
最后遍历的元素是3, 此时新的序列是0,3,7, 查找3成功, 退出.

不过, 很显然, 第二种方法并不能达到题目要求的nlg(n)的要求.但是, 它的优点在于, 不一定非得遍历完序列的所有元素就可以找到答案.

另外,这个题目给我的另一个启示就是,在很多问题中, 排序和搜索算法绝对是最基础的组成部分,你可能不会直接使用到它们, 但是会间接的使用或者借鉴到其中的想法帮助你解决问题.所以, 不管是效率比较低的插入算法也好, 还是快速排序也好, 都要进行研究, 并且掌握其中蕴藏的思想.


posted on 2008-09-29 10:40 那谁 阅读(3628) 评论(7)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: (算法导论习题解ex2.3-7)给定一个整数序列以及一个数X,确定该序列中是否有两个数的和为X  回复  更多评论   

排序,然后枚举+原序列二分(X-a[i])不行吗?
2008-09-29 11:53 | Ernls

# re: (算法导论习题解exercise2.3-7)给定一个整数序列以及一个数X,确定该序列中是否有两个数的和为X[未登录]  回复  更多评论   

首先nlogn的快排
其次设一个首指针head 设一个尾指针tail
while(head!=tail)
{
if(*head+*tail < num) head++;
elseif(*head+*tail>num) tail--;
else break;

}

if (head == tail)std::cout<<"Not found!";
else
std::cout<<*head<<" "<<*tail<<std::endl;

复杂度是o(nlogn+n)=o(nlogn)
2008-09-30 17:01 | Uo

# re: (算法导论习题解exercise2.3-7)给定一个整数序列以及一个数X,确定该序列中是否有两个数的和为X[未登录]  回复  更多评论   

@Uo
嗯,楼上这个方法也不错.
2008-09-30 20:09 |

# re: (算法导论习题解exercise2.3-7)给定一个整数序列以及一个数X,确定该序列中是否有两个数的和为X[未登录]  回复  更多评论   

算法导论给出的算法复杂度精确计算应为nlgn+2*n 额外辅助空间为o(n)
上面那个算法空间复杂度o(1),算法复杂度精确为nlgn+n
2008-10-01 01:27 | Uo

# re: (算法导论习题解exercise2.3-7)给定一个整数序列以及一个数X,确定该序列中是否有两个数的和为X  回复  更多评论   

@Uo
没有回潄,很不严密
2008-11-11 10:25 | Romeo

# re: (算法导论习题解exercise2.3-7)给定一个整数序列以及一个数X,确定该序列中是否有两个数的和为X  回复  更多评论   

1.先排序,
2.然后 按照 n / 2 对序列进行二分查找

3.然后根据查找的结果将 原序列分成A和B两个部分

4.然后对A中的每个元素a进行X-a在B中进行二分查找

5. 如果找到则结束

6.如果没有找到则根据在B中查找的结果将B二分为B1和B2

7然后对A中的下一个元素a1进行X-a1在B2中二分查找查找

8回到5

2009-10-02 04:26 | lzonline01

# re: (算法导论习题解exercise2.3-7)给定一个整数序列以及一个数X,确定该序列中是否有两个数的和为X  回复  更多评论   

如果原数组中有重复的两个数,正好他们相加等于X呢?这样博主的第一步”1) 首先将序列排序,去掉重复的元素.“就有问题了。

比如1,3,4,4,5,8 X = 8
2011-02-23 13:17 | wtommy

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