两个有序数组问题

两个已排序的整型数组，求交集，最快算法
输入：两个已排序的整型数组（int a[m], b[n]）
输出：两个数组的交集

 

当然也可是是判断两个有序数组是否包含的问题,解题思路差不多.

 

写过分治合并程序的一定知道merger函数,对就是这个思路

while(i

 {

   ....

   ....

 }

 

可以引申为链表的问题...ok上代码了

 

#include <stdio.h>
#include <stdlib.h>

#define N 10
#define M 5

void count_common(int A[], int B[])
{
  int i = 0;
  int j = 0;
  
  while(i<N && j<M)
   {
     if(A[i]<B[j])
       i++;
     else if(A[i]>B[j])
       j++;
     else
      {
       printf("%d\t",A[i]);
       i++;
       j++;
      }
   }
   
   printf("\n");
}
 
int check_in(int A[], int B[])
{
  int i = 0;
  int j = 0;
  int ret = 0;
  
  while(i<N && j<M)
   {
     if(A[i]<B[j])
       i++;
     else if(A[i]==B[j])
      {
       i++;
       j++;
      }
     else
      break;
   }
  
  if(j==M)
   ret = 1;
   
   return ret;
}
  
int main(int argc, char *argv[])
{
  int A[N];
  int B[5];
  int i;
    
  for(i=0;i<N;i++)
   A[i] = i+1;
   
  for(i=0;i<M;i++)
   B[i] = 2*i+1;
  
  //B[1] = 4;

  //B[M-1] = 11;

  printf("common is:\n");
  count_common(A, B);
  
  check_in(A, B)?printf("in\n"):printf("not in\n");
   
  system("PAUSE");    
  return 0;
}