三道简单算法题(二)

//1：试着用最少的比较次数去寻找数组中的最大值和最小值。 
void FindMaxMin(int *A,int size,int* Max,int* Min)
{ 
    int i=(size & 1)?1:0;
    *Max=*Min=A[0]; 
    for(;i<size;i=i+2)
    {
        if(A[i]>A[i+1])
        {
            if(A[i]>*Max) 
                *Max=A[i]; 
            if(A[i+1]<*Min) 
                *Min=A[i+1]; 
        }else{
            if(A[i+1]>*Max) 
                *Max=A[i+1]; 
            if(A[i]<*Min) 
                *Min=A[i]; 
        }
    }  
}

void FindMaxMinTest(){
    int A[9]={2,4,6,8,9,1,3,5,7};
    int Max=0;
    int Min=0;
    FindMaxMin(A,9,&Max,&Min);
    cout<<Max<<endl;
    cout<<Min<<endl;
}

//2：给一个整数数组，求数组中重复出现次数大于数组总个数一半的数
int MoreThanHalf(int *A,int size)
{ 
    int num=A[0];
    int count=1;
    for(int i=1;i<size;i++)
    { 
        if(num==A[i])
        {
            count++;
        }else{
            count--;  
            if(count==0)
            { 
                num=A[i];
                count=1;
            }
        } 
    }
     
    count=0;
    for(int i=0;i<size;i++)
    {
        if(A[i]==num)
            count++;
    }  
    return count>(size/2)? num:-1;
}

void MoreThanHalfTest()
{
    int A[9]={ 1, 1,2, 1, 2, 2, 1, 2, 2 };
    cout<<MoreThanHalf( A,9);
}

//3：给一个很大的数组，里面有两个数只出现过一次，其他数都出现过两次，把这两个数找出来
void FindTwoNum(int* A,int size, int* first,int* second)
{
    int excVal=A[0];
    for(int i=1;i<size;i++)
    {
        excVal^=A[i];
    }
    int s1=1;
    int s2=excVal;
    while((s2&1)==0)
    {
        s2>>=1;
        s1<<=1;
    }
    *first=excVal;
    for(int i=0;i<size;i++)
    { 
        if(s1&A[i]) 
            *first^=A[i];
    }
    *second=excVal^*first;
}

void FindTwoNumTest()
{
    int A[12]={2,1,1,2,3,3,5,7,4,4,7,9};
    int first=0,second=0;
    FindTwoNum(A,12,&first,&second);
    cout<<first<<endl;
    cout<<second;
}