百度笔试题求两个整数集合的公共元素

ubuntuer

求两个整数集合的公共元素。
大致思路就是对一个集合求hash,然后遍历另一个集合,如果在hash中就打印...程序内面有很多无用的个人认为是技巧的技巧


#include stdio.h>
#include stdlib.h>
#include time.h>
#define N1 10
#define N2 5
#define MAX 15
typedef struct hash
{
  int num;
  struct hash* next;
}HASH;
int C[MAX];
HASH* H[10];
int swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
  
int get_rand(int start, int end)
{
  int rand_num = rand()%(end-start+1)+start;
  printf("rand_num is %d\n",rand_num);
  swap(C+start, C+rand_num);
  
  return C[start];
}
void init_array_a(int A[])
{
  int i = 0;
  for(i=0;iN1;i++)
   A = get_rand(i,MAX);
     
}
void init_array_b(int B[])
{
   int i;
   for(i=0;iN2;i++)
    B = get_rand(i,MAX);
}

void init_hash()
{
  int i;
  for(i=0;i10;i++)
   {
    H = (HASH*)malloc(sizeof(HASH));
    H->next = NULL;
   }
}
void add_hash(int num)
{
  int hash_num = num%10;
  HASH* p = (HASH*)malloc(sizeof(HASH));
  p->num = num;
  p->next = H[hash_num]->next;
  H[hash_num]->next = p;
}
int exist(int num)
{
int hash_num = num%10;
HASH* p = H[hash_num]->next;
while(p!=NULL)
  {
   if(p->num == num)
     return 1;
   p = p->next;
  }
  return 0;
}
int main(int argc, char *argv[])
{
  int A[N1];
  int B[N2];
  int i;
   
  srand((unsigned int)time(NULL));
  for(i=0;iMAX;i++)
   C = i+1;
   
init_array_a(A);
init_array_b(B);
init_hash();
   
  printf("array A is:\n");
  for(i=0;iN1;i++)
   {
    printf("%d ",A);
    add_hash(A);
   }
  printf("\narray B is:\n");
  for(i=0;iN2;i++)
    printf("%d ",B);
  
   
  printf("\n交集is:\n");
  for(i=0;iN2;i++)
   {
     if(exist(B))
         printf("%d ",B);
   }
  system("PAUSE");   
  return 0;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76292/showart_2022697.html