int Count (int f[], int g[], int m, int n)
{
    int i, j;
    int count= 0;
    
    for (i=0; i<m; i++)
    {
        for (j=0; j<n; j++)
        {
            if (f[i] == g[j])
            {
                count++;
                break;
            }
        }
    }
    
    return count;
}

int Count (int f[], int g[], int m, int n){
   int i;
   int j;
   int result=0;
   while(i<=m && j<=n){
     if(f[i]=g[j]){
        result++;
        }
     else if(f[i]<g[j]){
            i++;
            }
     else{
          j++;  
          } 
   return result; 
      }


}

运行环境：ＴＣ２．０

第一题：#include <time.h>
#include <stdio.h>
#include <dos.h>
int majority(int vote[],int n)
{int i,j,count=0;
 for(i=-1;(i<n)&&(count<=n/2);)
 {i++;
  for(j=0,count=0;j<n;j++)
  if(vote[i]==vote[j]) 
  count++;
 }
if(i!=n) return count;
else return 0;
}
void main()
{int vote[5]={1,8,1,100,1};
 clock_t start, end;
 start = clock();
 printf("%d\n",majority(vote,5));
 end = clock();
 printf("The time was: %f\n", (end - start) / CLK_TCK);
 return 0;
}



第二题：
#include<stdio.h>
int count(int f[],int g[],int m,int n)
{
 int i=j=0,count=0;
 while((i<m)&&(j<n))
  {
   if(f[i]<g[j]) i++;
   else if(f[i]>g[j]) j++;
        else {i++;
             j++;
             count++;
             }
  }
 return count;
}
void main()
{int f[5]={1,3,4,7,9};
 int g[4]={3,5,7,8};
 printf("%d",count(f,g,5,4));
}

O(n)的算法
把每一个在数组中可能出现的数字当作一个桶，扫描数组，把每个数字扔到对应的桶中，然后检查所有的桶，如果存在一个桶中的数字的数目大于n/2, 就输出这个数目，否则返回0
现在数字的范围即对应的桶的数目非常大，有2^32个，解决这个问题的方法是分两步，首先检查每个数字的高16位，然后检查低16位，这样虽然要多扫描一次数组，但算法的时间复杂度仍然是线性，空间复杂度大大缩小，从2^32降到64k, 占用的空间是256KB,足够放在大多数cpu 的L2$中(除了celeronD和比较老的机器)
时间复杂度为O(2n+2*64k)
当n比较大时，省掉常数项即为O(n)
当n比较小时，相对于128k可以忽略掉时，复杂度为O(128k), 可以看到这个时候先排序在检查也许会更快，qsort复杂度为O(nlgn), 其实这个时候，人是无法感觉出他们的差别的，这个临界点大约在n=10k左右，简单起见，我的程序并没有根据n的大小选用不同的方法，统一使用了上面描述的O(n)算法.

下面这段程序在n=0x6000000, 大约96M左右时，在我的P3M 1.2G机器上需要4-5s

int count[65536];
int Majority (int vote[], int n)
{
    int i, mask;
    int half = n / 2;

    memset(count, 0, sizeof(count));
    for (i=0; i<n; i++)
        count[(vote[i] >> 16) & 0xffff] ++;

    for (i=0; i<65536; i++)
    {
        if (count[i] > half)
            break;
    }
    if (count[i] <= half)
        return 0;
    mask = i << 16;

    memset(count, 0, sizeof(count));
    for (i=0; i<n; i++)
        if ((vote[i] & 0xffff0000) == mask)
            count[vote[i] & 0xffff] ++;

    for (i=0; i<65536; i++)
    {
        if (count[i] > half)
            break;
    }
    if (count[i] <= half)
        return 0;

    return count[i];
}

赠送题：
编译环境VC6.0
int Count (int f[], int g[], int m, int n)
{
    int result = 0;
    int *p1 = f,*p2 = g;
    for(int i = 0;i < m;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(*(p1+i) == *(p2+j))
                    result ++;
        }
    }
    return result;
}

//#include "stdafx.h"
#include "math.h"
#include "memory.h"
#include "stdio.h"
#include "stdlib.h"
#include "search.h"
//#include "assert.h"

/*
    半数问题，给定整型数组vote[], 其大小为n，数组中任一元素均为自然数i(i = 1,2,3,...)。
规定函数接口：int Majority (int vote[], int n)
    在vote[]中，可能存在一个自然数i，其个数m 超过半数，即m > n/2。若存在这样的i，函数Majority返回m，否则函数返回0。
例：
    vote[5] = {1,8,1,100,1}; 其大小为 5。
    因为自然数1的个数为3，超过半数，那么调用Majority将返回 3。
题目要求：编写规定函数接口 Majority。
*/

#define SMALL_PRIME_COUNT 54    //小质数表的包含的质数个数
#define MAX_SMALL_PRIME   256    //最大质数
#define MY_NULL 0 

typedef unsigned long DWORD;

typedef struct item_tag
{
    int n;
    int next;    //相当于指针，指向下一个结点
}ITEM;

typedef struct _link_tag //链表
{
    int count; //元素个数
    int head;  //头    
    int tail;  //尾
}LINK;

typedef struct int_pool_tag
{
    int item_count;
    ITEM *pData;  //存储池
    int freeHead; //自由结点链表头
    //-----------------------
    struct 
    {
        LINK *data;   //链表数组
        int maxSize;  //链表的个数
        int count;    //实际使用到的链表的个数
    }linkArr;
    
}INT_POOL;

int g_primeArr[SMALL_PRIME_COUNT]=
{
    2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31,
    37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
    83, 89, 97,101,103,107,109,113,127,131,137,
    139,149,151,157,163,167,173,179,181,191,193,
    197,199,211,223,227,229,233,239,241,251,
};

int getPrimeGT_n(int n) //得到大于等于n的一个质数
{
    if (n<=7)
    {
        switch(n)
        {
        case 2: return 2;
        case 3: return 3;
        case 4: case 5: return 5;
        case 6: case 7: return 7;
        } 
    }
    
    while (1)
    {
        int i,sqrt_n,flag;
        sqrt_n=(int)sqrt(n)+1;
        while (sqrt_n*sqrt_n>n) sqrt_n--;
    
        for (flag=1,i=0;;i++)
        {
            if (n % g_primeArr[i] ==0)
            {
                flag=0;    break;
            }
            if ( i==SMALL_PRIME_COUNT-1 || g_primeArr[i]>=sqrt_n)
                break;
        }
        if (flag)    break;
        n++;
    }
    return n;
}

void InitPool(INT_POOL *pool,int n)
{
    int i;
    pool->item_count=0;
    pool->pData= new ITEM[n+1];
    pool->item_count=n;
    
    for (i=1;i<n;i++)
        pool->pData[i].next=i+1;
    pool->pData[n].next=MY_NULL;
    pool->freeHead=1;  //0号结点弃之不用
    pool->linkArr.count=0;
    pool->linkArr.maxSize=0;
    pool->linkArr.data=NULL;
}

void FreePool(INT_POOL *pool)
{
    if (pool->pData!=NULL)
        delete[] pool->pData;
    if (pool->linkArr.data!=NULL)
        delete[] pool->linkArr.data;
    memset(pool,0,sizeof(INT_POOL));
}

inline int mallocNode(INT_POOL *pool)//从自定义的池中分配一个结点
{
    int r=pool->freeHead;
    pool->freeHead=pool->pData[r].next;
    return r;
}

inline void FreeNode(INT_POOL *pool,int idx) //释放一个结点到自定义的池中
{
    pool->pData[idx].next=pool->freeHead;
    pool->freeHead=idx;
}

//将一个结点插入到链表no号链表
inline void InsertToNewLink(INT_POOL *pool,int linkNo,int num,int newNode)
{
    pool->pData[newNode].n=num;
    pool->pData[newNode].next=MY_NULL;

    if  (pool->linkArr.data[linkNo].head==MY_NULL)
    {
        pool->linkArr.data[linkNo].head=newNode;
        pool->linkArr.data[linkNo].tail=newNode;
        pool->linkArr.data[linkNo].count=1;
    }
    else    
    {
        int t=pool->linkArr.data[linkNo].tail;
        pool->pData[t].next=newNode; 
        pool->linkArr.data[linkNo].tail=newNode;
        pool->linkArr.data[linkNo].count++;
    }
}

//查找包含数据项最多的链表和包含的元素的个数
void FindMaxRemain(INT_POOL *pool,int *linkNo,int *count,int module)
{
    int i;
    for (*linkNo=0,*count=0,i=0;i<module;i++)
    {
        if (pool->linkArr.data[i].count > *count)
        {    *linkNo=i;    *count=pool->linkArr.data[i].count;    }
    }
}

void SearchBestModula(int n,int iMax,int modular[], int *count)
{
    int i,j,m;
    int modu[5][5];
    double t[5],t2;
    double s1,s2;
    if (n<=64*1024)
    {    s1=18; s2=14;}
    else 
    {  s1=10; s2=8;    }
        
    for (i=2;i<=4;i++)
    {
        m=(int)exp( log(iMax)/i);
        for (j=0;j<4;j++)
        {
            modu[i][j]=getPrimeGT_n(m);
            m=modu[i][j]+1;
        }
        
        t[i]=  (double)n      + modu[i][0]/s1;
        t2=    (double)n* 0.7 + modu[i][3]/s2;
        t[i] += t2*(i-1);
    }
    
    for (t2=t[2],j=2,i=2;i<=4;i++)
        if (t[i]<t2)    { t2=t[i];    j=i;}

    *count=j;
    modular[0]=modu[j][0];
    modular[1]=modu[j][1];
    modular[2]=modu[j][2];
    modular[3]=modu[j][3];
}

//第一次分类
void firstSort(INT_POOL *pool,int arr[],int n,
    int module,
    int maxModule)
{
    int i,j,newNode;

    if ( pool->linkArr.data!=NULL)
        delete[] pool->linkArr.data;
    
    pool->linkArr.data= new LINK[maxModule];
    memset(pool->linkArr.data,0,sizeof(LINK)*maxModule);

    pool->linkArr.count=module;
    pool->linkArr.maxSize=maxModule;
    
    for (i=0;i<n;i++)
    {
        j=arr[i] % module;
        newNode=mallocNode(pool);
        InsertToNewLink(pool,j,arr[i],newNode);
    }
}

//下一次分类
void nextSort(INT_POOL *pool,
    int module,        //另一个模    
    int oldLinkNo)  //上次元素最多的链表
{
    int i,head,num,newNode;
    LINK oldLink;    //上一次分类时，元素最多的列表
    
    oldLink.head = pool->linkArr.data[oldLinkNo].head;
    oldLink.tail = pool->linkArr.data[oldLinkNo].tail;

    //置所有链表为空，但不释放其空间，
    memset(pool->linkArr.data,0,sizeof(LINK) * pool->linkArr.maxSize); 
    
    //assert(module<=pool->linkArr.maxSize);
    pool->linkArr.count=module;
    head=oldLink.head;
    
    while (head!=MY_NULL)
    {
        int h;
        num=pool->pData[head].n;
        h=head;
        head=pool->pData[head].next; //从旧的链表中取下一个结点
        FreeNode(pool,h);         //释放该结点
        
        i=num % module;
        newNode=mallocNode(pool);
        InsertToNewLink(pool,i,num,newNode);
    }
}

int dealSmallNumSet(int arr[],int n,int maxValue)
{
    int i,max;
    int *p=new int[maxValue+1];

    if (p==NULL)
    { printf("No memory\n");    return 0;}

    memset(p,0,sizeof(int)*(maxValue+1));

    for (i=0;i<n;i++) p[ arr[i] ]++;
    for (max=0,i=0;i<=maxValue;i++)
        if (p[i]>max)
            max=p[i];

    if (max>n/2)    return max;
    else            return 0;
}

int cmp(const void*x, const void *y)
{
    return (*(int*)x - *(int*)y);
}

int findHalf(int arr[],int n)
{
    int i,pre,max,count;
    int *p=new int[n];
        
    memcpy(p,arr,sizeof(int)*n);
    qsort((void *)(p),n,sizeof(int),cmp);
    
    max=0;       count=1;
    for (pre=p[0],i=1;;i++)
    {
        while ( i<n && p[i]==pre)
        {    i++; count++;}
        
        if (i==n)        break;
        if (count>max)    max=count;
        count=1;pre=p[i];
    }
    
    delete[] p;
    if (count>max)
        max=count;
    if (max>n/2)
        return max;
    else 
        return 0;
}

int Majority(int vote[], int n)
{
    int i,iMax;
    int modular[4];

    INT_POOL dataPool;
    int linkNo,moduCount,itemCount;

    for (iMax=vote[0],i=1;i<n;i++)
    {
        if (vote[i]>iMax)
            iMax=vote[i];
    }

    if (iMax<=n)
        return dealSmallNumSet(vote,n,iMax);

    if (n<1500)
        return  findHalf(vote,n);

    InitPool(&dataPool,n);
    SearchBestModula(n,iMax,modular,&moduCount);

    firstSort(&dataPool,vote,n,modular[0],modular[moduCount-1]);
    FindMaxRemain(&dataPool,&linkNo,&itemCount,modular[0]);

    if (itemCount<=n/2)
        goto thisExit;

    for (i=2;i<=moduCount;i++)
    {
        nextSort(&dataPool,modular[i-1],linkNo);
        FindMaxRemain(&dataPool,&linkNo,&itemCount,modular[i-1]);

        if (itemCount<=n/2)
            break;
    }

thisExit:    
    FreePool(&dataPool);
    
    if ( itemCount<=n/2)
        return 0;
    else
        return itemCount;
}