寻找数组中的最大值和最小值

 

解法一：将寻找数组中的最大值和最小值看成是两个独立的问题。分别求出最大值和最小值即可。这样需要2*N次的比较才能求出最大的数和最小的数。

void FindMinMax(int A[],int size,int &min,int &max)
{
    min=A[0];
    max=A[0];
for(int i=1;i<size;i++)
    {
if(A[i]>max)
            max=A[i];
if(A[i]<min)
            min=A[i];
    }
}

解法三：解法已经将比较次数降低到1.5N次，但是它已经破坏原来的数组。可以不需要调整数组元素的位置，直接用两个变量Max和Min来存储当前的最大值和最小值。同一组的两个数比较之后，不再调整顺序，而是用较小者与当前的Min比较，如果该数小于当前Min，则更新Min。Max同理。该算法的比较次数扔为1.5N.

void findMaxMin(int a[],int size,int &min,int &max)
{
for(int i=0;i<size-1;i++)
    {
if(a[i+1]>a[i])
        {
if(a[i+1]>max)
                max=a[i+1];
if(a[i]<min)
                min=a[i];
        }
else
        {
if(a[i]>max)
                max=a[i];
if(a[i+1]<min)
                min=a[i+1];
        }
    }
}

 扩展问题：如果需要找出N个数组中第二大数，需要比较多少次？

int FindSecondNum(int a[],int size)
{
int max=a[0];
int secondNum=0;
for(int i=1;i<size;i++)
    {
if(a[i]>max)
        {
            secondNum=max;
            max=a[i];

        }
else
        {
if(secondNum<a[i])
                secondNum=a[i];
        }
    }
return secondNum;
}