随笔-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 楚天清秋 阅读(944) 评论(0)  编辑 收藏 引用 所属分类: C,C++算法

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