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

心存感恩crossover.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

openspace

博客访问： 144626
博文数量： 35
博客积分： 2386
博客等级：大尉
技术积分： 380
用户组：普通用户
注册时间： 2009-05-05 06:11

文章分类

全部博文（35）

misc（1）
Bash（0）
Database（1）
Search Engine（4）
Django（2）
Linux Kernel（0）
Python（4）
Data Structure（2）
Linux（2）
C/C++（6）
Algorithm（10）
Machine Learning（1）
Data Mining（0）
未分配的博文（2）

文章存档

2011年（1）

2010年（2）

2009年（32）

我的朋友

最近访客

推荐博文

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

分类：

2009-05-15 09:17:27

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

I 对集合S中的元素进行排序，选择复杂度为O(nlgn)的排序算法

II 遍历排序后S的元素，，对每个元素e，计算x-e，然后通过折半查找检测x-e是否也属于集合S
复杂度为O(nlgn)

阅读(1477) | 评论(0) | 转发(0) |

上一篇：0-1背包问题

下一篇：逆序对

给主人留下些什么吧！~~

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6