【我解C语言面试题系列】012 查找整数数组中第二大的数

查找整数数组中第二大的数

 

题目：写一个函数找出一个整数数组中，第二大的数。【Mirosoft】

PS：1、” 66,66,66,66,66 ”，则没有第二大数。

2、” 99,99,88,86,68,66 ”，则最大数是88。

下面我先给出查找最大数字的程序：

int GetFirstMaxNumber(int buffer[])

{

    int i,max;

 

    max = buffer[0];

    for(i=1;i<ARRSIZE;i++)

    {

       if(buffer[i] > max)

           max = buffer[i];

    }

   

    return max;

}

这个算法非常经典，时间复杂度是：O(N)。对于查找一个数组中的最大数字，我们至少要做的就是把数组扫描一遍，能在只扫描数组一遍的情况下就能解决问题的则算法已经是一个不错的算法的了。

查找第二大的数的算法就是在查找最大数的算法的基础上实现的，下面给出查找第二大数的程序：

 

#define  ARRSIZE             10

#define  MINNUMBER          0xFFFFFFFF

#define  FIND_SUCESS         1

#define  FIND_FAIL          0

int GetSecondMaxNumber(int buffer[],int *secondMax)

{

    int i,max;

 

    max = buffer[0];

    *secondMax = MINNUMBER;

    for(i=1;i<ARRSIZE;i++)

    {

       if(buffer[i] > max)

       {

            *secondMax = max;

           max = buffer[i];

       }

       else if (buffer[i] > *secondMax  && buffer[i] < max)

            *secondMax = buffer[i];

    }

    if(*secondMax == MINNUMBER) //The numbers are all the same.

       return FIND_FAIL;

 

    return FIND_SUCESS;

}

查找第二大数实际上是伴随在查找最大数的过程中的。

1、如果当前元素大于最大数 max，则让第二大数等于原来的最大数 max，再把当前元素的值赋给 max。

2、 如果当前的元素大于第二大数secondMax的值而小于最大数max的值，则要把当前元素的值赋给 secondMax。――判断条件不能仅仅只是大于第二大的数secondMax，否则我们便无法处理” 99,99,88,86,68,66 ”这种情况。

PS：这个函数在调用时需要判断函数的返回值是否是 FIND_SUCESS 才能使用。