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

嵌入式linux系统与图像处理seen.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

zhiqiang0071

博客访问： 1975401
博文数量： 185
博客积分： 10707
博客等级：上将
技术积分： 1777
用户组：普通用户
注册时间： 2008-09-19 17:31

文章分类

全部博文（185）

Algorithm（3）
others（4）
Audio（1）
Software Testing（1）
Soft Architectur（2）
Hardware（0）
linux filesys（5）
Video（7）
TCP/IP（1）
GUI（8）
Linux others（28）
Linux Device Dri（12）
Linux Programmin（17）
Linux Kernel（24）
Embedded（32）
USB（9）
Davinci（15）
未分配的博文（16）

文章存档

2014年（1）

2012年（6）

2011年（27）

2010年（13）

2009年（75）

2008年（63）

我的朋友

最近访客

推荐博文

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

分类：

2010-07-20 08:35:33

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

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

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

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

上一篇：字符设备驱动模型浅析

下一篇：输出整数对应二进制数中1的个数

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

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

16024965号-6