两个有序数组问题

时间：2009-08-13 来源：ubuntuer

两个已排序的整型数组，求交集，最快算法
输入：两个已排序的整型数组（int a[m], b[n]）
输出：两个数组的交集当然也可是是判断两个有序数组是否包含的问题,解题思路差不多. 写过分治合并程序的一定知道merger函数,对就是这个思路 while(i<N&&j<M) { .... .... } 可以引申为链表的问题...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;
}