[编程之美] PSet2.10 寻找数组中的最大值和最小值

分析参考自：http://blog.csdn.net/insistgogo/article/details/7693743 代码自写

问题描述：给出一个数组，包含N个整数，那么需要比较多少次找到最大值和最小值

注意：要想得到最大值和最小值，遍历一遍数组是不可避免的。我们能减少的就是减少比较次数来提高效率。

方法一、遍历一遍数组，同时得到最大值和最小值

具体是，定义一个max 和 min，每遍历一个数，就分别和max 和 min比较一次，直到处理完所有的数据

比较次数： N+N = 2N

//方法一：直接比较，对每个数都要比较一次，总共需要比较2N次
void findMinMax(int Arr[] , int arrLen ,int &min , int &max)
{
	min = Arr[0];
	max = Arr[0];
	for(int i=1 ; i<arrLen ; i++){
		if(min > Arr[i])
			min = Arr[i];
		if(max < Arr[i])
			max = Arr[i];
	}
}
           

方法二、我们可以把数组中的数据两两分组，分组内找出最大值 和 最小值，之后在最大值的那部分找出最大值，在最小值那部分找出最小值

比较次数：

两两比较，较小值放到左边，较大放右边，这时比较N/2次

之后，得到的最大值部分是 N/2个数，最小值部分是N/2个数

之后在 最大值部分 取出最大值。比较次数N/2

   在 最小值部分 取出最小值。比较次数N/2

比较次数：1.5N

评价：虽然比较次数下降了，但是破坏了原数组，而且由于在比较过程中有数据的交换，效率还是会拖累的。

//方法二：两个为一组，较小的放在左边，较大的放在右边，然后从奇数下标中找min，偶数下标找max
//需要比较3N/2次，但是有数字交换，因此感觉会挺慢的。，注意数组长度需分奇偶
void findMinMax(int Arr[] , int arrLen ,int &min , int &max)
{
	min = Arr[0];
	max = Arr[0];
	int temp;
	int end;
	if(arrLen&1)//数组元素有奇数个
		end = arrLen-2;
	else
		end = arrLen-1;
	for(int i=0 ; i<end ; i=i+2){//两个为一组，注意边界条件
		if(Arr[i] > Arr[i+1]){
			temp = Arr[i];
			Arr[i] = Arr[i+1];
			Arr[i+1] = temp;
		}
	}
	for(int j=0 ; j<end ; j++){//扫描一次，将奇数下标的取出来比较max，偶数下标取出来比较min
		if(j&1){//奇数下标
			if(Arr[j] > max)
				max = Arr[j];
		}
		else{//偶数下标
			if(Arr[j] < min)
				min = Arr[j];
		}
	}
	if(arrLen&1){
		max = max>Arr[arrLen-1]?max:Arr[arrLen-1];
		min = min<Arr[arrLen-1]?min:Arr[arrLen-1];
	}
}
           

方法三、引入俩变量min 和 max，每次也是处理两个数据，直到所有的数据全部都处理完

具体思路：

引入两个变量Min 和 Max

取出两个数，比较一次，得出最大值和最小值

最大值和Max比较，最小值和Min比较，如果比最值还要大或小，则进行更新

比较次数：每处理两个数，比较3次，则N/2 *3 = 1.5N次

优点，不会破坏原数组，较好。

//方法三：两个数一组，min与max分别与较小数与较大数比较，总共3N/2次比较
void findMinMax(int Arr[] , int arrLen ,int &min , int &max)
{
	min = Arr[0];
	max = Arr[0];
	for(int i=0 ; i<arrLen-1 ; i=i+2){//两个为一组，注意边界条件
		if(Arr[i] > Arr[i+1]){
			if(max < Arr[i])
				max = Arr[i];
			if(min > Arr[i+1])
				min = Arr[i+1];
		}
		else{
			if(max < Arr[i+1])
				max = Arr[i+1];
			if(min > Arr[i])
				min = Arr[i];
		}
	}
	if(arrLen&1){
		max = max>Arr[arrLen-1]?max:Arr[arrLen-1];
		min = min<Arr[arrLen-1]?min:Arr[arrLen-1];
	}
}
           

方法四、使用分治算法，其实和方法三是一样的，分治是一直到两个数的时候才做，且做完了 把结果合并下就好。

思路：在N个数中求最大值和最小值，我们只需求出前后N/2个数的Min和Max，然后取较小的Min，较大的Max即可

比较次数：和方法三一样，比较次数没有变化

分析：

f(2) = 1; 

f(n) = 2*f(n/2) + 2; 

 第2个2的意思是：递归分成的两部分求出最值后，还有结合下求出一个整体的最值，这时要有两次比较 

可以推出f(n) = 1.5*n -2;  可见总的比较次数仍然没有减少。

//方法四：分治法，将数组分为两半，求得左半的LMax与LMin与右半的RMax与RMin，然后比较得出结果，需要比较3N/2-2次
void findMinMax4(int Arr[] , int low , int high ,int &min , int &max)
{
	//递归终止条件
	if(high-low <= 1){//两个元素或一个元素
		if(Arr[high] > Arr[low]){
			max = Arr[high];
			min = Arr[low];
			return;
		}
		else{
			max = Arr[low];
			min = Arr[high];
			return;
		}
	}
	int mid = low + (high-low)/2;//防止上溢
	int LMax,LMin,RMax,RMin;
	findMinMax4(Arr , low , mid , LMin , LMax);
	findMinMax4(Arr , mid+1 , high , RMin , RMax);
	min = LMin>RMin?RMin:LMin;
	max = LMax>RMax?LMax:RMax;
}
           

扩展问题：如果需要找出N个数组中第二大数，需要比较多少次？是否可以使用类似的分治思想来降低比较次数呢？

//下面的方法是直接比较的方法，对于每一个数需要与Max和secondMax比较一次，需要比较2N次，也可采用以上算法的变形，两两一组的形式···
int FindSecondMax(int Arr[],int size)
{
	int Max,secondMax;
	Max = Arr[0];
	secondMax = Arr[0];
	for(int i=1 ; i<size ; i++){
		if(Arr[i]>Max){
			secondMax = Max;
			Max = Arr[i];
		}
		else if(secondMax < Arr[i]){
			secondMax = Arr[i];
		}
	}
	return secondMax;
}
           

       至于能否用分治思想，我来试试用用看。考虑分成两部分，得到左半部分的LMax以及LSecondMax，有半部分RMax以及RSecondMax，然后经过比较这四个数得到第二大就可以了。由于LMax>SecondMax ; RMax>RSecondMax，因此只需要比较LMax>RMax，取较小的那个就行了。咋看之下好像有点道理，仔细一想如果LMax>RMax并不能说明整个数组第二大值为RMax，因为左半部分的第二大值可能比右半部分的最大值还要大哦。

//分治法解决第二大问题,正如前面所言，需要比较四个数，要注意的一点就在于并不是LMax>RMax就说明RMax为整个数组的第二大
void FindSecondMax(int Arr[],int low,int high,int &secondMax,int &Max)
{
	if(high-low <=1){//如果只有两个数或一个数
		if(Arr[high] > Arr[low]){
			Max = Arr[high];
			secondMax = Arr[low];
			return;
		}
		else{
			Max = Arr[low];
			secondMax = Arr[high];
			return;
		}
	}
	int mid = low + (high-low)/2;//防止上溢
	int LMax,LSecMax,RMax,RSecMax;
	FindSecondMax(Arr , low , mid , LSecMax , LMax);
	FindSecondMax(Arr , mid+1 , high , RSecMax , RMax);
	if(LMax > RMax){
		Max = LMax;
		if(LSecMax > RMax)
			secondMax = LSecMax;
		else
			secondMax = RMax;
	}
	else{
		Max = RMax;
		if(RSecMax > LMax)
			secondMax = RSecMax;
		else
			secondMax = LMax;
	}
}