【编程之美】读书笔记：寻找数组中的最大值和最小值

        问题：对于一个由N个整数组成的数组，需要比较多少次才能把最大值和最小值的数找出来呢？

        

       解法一：将寻找数组中的最大值和最小值看成是两个独立的问题。分别求出最大值和最小值即可。这样需要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];
}
}

        解法二：由于最大的数和最小的数不会是同一个数(N!=1)，可以把数组分成两部分，然后再从这两部分中分别找出最大的数和最小的数。首先按顺序将数组中相邻的两个数分在同一组，接着比较同一组中奇数位数字和偶数位字，将较大的房子偶数位上，较小的数放在奇数位上，经过N/2次比较的预处理后，较大的数都放到了偶数位置上，较小的数则放到了奇数位置上，最后从奇偶数位上分别求出Max和min,各需要比较N/2次。整个算法共需要比较1.5*N次。

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

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

void FindMinMax(int A[],int size,int &min,int &max)
{
      max=-INF;
     min=INF;
for(int i=0;i<size-1;i++)
{   
if(A[i]<A[i+1])
{
          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个数中求最小值Min和Max，只需要分别求出前后N/2个数的Min和Max，然后比较较小的Min,和较大的Max即可。

void FindMinMax(int A[],int low,int high,int &min,int &max)
{
 int maxL,maxR,minL,minR;
    if(high-low<=1)
{
if(A[low]<A[high])
{
min=A[low];
max=A[high];
return ;
}
else
{
            min=A[high];
max=A[low];
return ;
}

}
FindMinMax(A,low,low+(high-low)/2,minL,maxL);
FindMinMax(A,low+(high-low)/2+1,high,minR,maxR);


if(maxL>maxR)
max=maxL;
else
max=maxR;


if(minL<minR)
min=minL;
else
min=minR;
}

该算法的比较次数为1.5N-2次，对于分治法，总的比较次数仍然没减少。


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

int FindSecondMax(int A[],int size)
{
  int i=0;
  int Max = A[0];
  int secondMax;

  for(i=1;i<size;i++)
  {
   if(Max <= A[i])
   {
    secondMax = Max;
    Max= A[i];
   }
   else
   {
    if(secondMax <=A[i])
    {
     secondMax = A[i]; 
    }
   }
  }
  return secondMax;
}

该算法的时间复杂度为O(N)。