判断两个数组中是否存在相同的数字 - wifecooky

随笔-22 评论-7 文章-0 trackbacks-0

给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？

O(n)算法。因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。

bool findcommon(int a[], int size1, int b[], int size2)

{

int i=0,j=0;

while(i<size1 && j<size2)

{

if(a[i]==b[j])

return true;

if(a[i]>b[j])

j++;

if(a[i]<b[j])

i++;

}

return false;

}

posted on 2010-06-09 12:16 楚天清秋阅读(934) 评论(0) 编辑收藏引用所属分类: C，C++ 、算法

只有注册用户登录后才能发表评论。


相关文章: 关于运行时类型识别typeid cout重定向到文件 (转) 判断两个数组中是否存在相同的数字浮点数在计算机中存储方式关于sizeof(类)的大小 c++虚函数表探究什么是智能指针(Solmyr 的小品文系列之五：垃圾收集) template必须定义于头文件中[转] 如何判断文件是否存在？

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜