寻找数组中的最大值和最小值
一 问题描述
试着用最小的比较次数去寻找数组中的最大值和最小值。
方法1：
分别遍历两次数组，分别求取数组中的最大值和最小值。这样其比较次数为2*N
方法2：
首先内存中维持两个变量，max 和 min 。
将数组中相邻的两个元素两两配对，对没对数据进行比较，并将数据对中的较大值和max比较，
将较小值跟min进行比较。此时 比较的次数为1.5 * n 。
方法3：
利用分治方法，类似归并排序。
逐次将数组分成两部分，然后比较两部分的最大值和最小值。
代码如下：
#include <iostream>
using namespace std ;
/**//*
利用分治法求一个数组的最大最小值
其比较次数仍然为1.5 * n
*/
struct Res
{
int max ;
int min ;
Res(int max , int min):max(max) , min(min) {}
Res() {}
} ;
Res maxmin(int * arr , int low , int high)
{
int i = low ;
int j = high ;
if(i < j)
{
if(i == j - 1)
{
if(arr[i] < arr[j])
return Res(arr[j] , arr[i]) ;
else
return Res(arr[i] , arr[j]) ;
}
int mid = (i + j ) >> 1;
Res left = maxmin(arr , low , mid) ;
Res right = maxmin(arr , mid + 1 ,high) ;
Res res ;
if(left.max > right.max)
res.max = left.max ;
else
res.max = right.max ;
if(left.min > right.min)
res.min = right.min ;
else
res.min = left.min ;
return res;
}
}
int main()
{
int arr[] = {6 , 5 , 8 ,3 , 9 ,7} ;
Res res = maxmin(arr , 0 , 5) ;
cout<<res.max<<" "<<res.min<<endl ;
getchar() ;
return 0 ;
}
二 求取数组中的第二大数字
也可以两两结合，比较的次数也为1.5N ，但是无法使用分治方法解决。代码如下：
/**//*
求取数组中的第二大的数字 , 也可以两两比较
但是不能使用分治法
*/
#include <iostream>
using namespace std ;
int max2(int * arr , int n)
{
if(!arr || !n )
return -1;
int begin ;
int max1 , max2; //存储最大值和最小值
if(n & 1) //奇数
{
begin = 1;
max1 = max2 = arr[0] ;
}
else
{
begin = 2;
if(arr[0] > arr[1])
{
max1 = arr[0] ;
max2 = arr[1] ;
}
else
{
max1 = arr[1] ;
max2 = arr[0] ;
}
}
for(int i = begin ; i < n ; i += 2)
{
int m1 , m2 ;
if(arr[i] > arr[i + 1]) //1次比较
{
m1 = arr[i] ;
m2 = arr[i+1] ;
}
else
{
m1 = arr[i+1] ;
m2 = arr[i] ;
}
if(m1 > max1) //比较2次大小
{
max1 = m1 ;
if(m2 > max1)
max2 = m2 ;
else
max2 = max1 ;
}
else //m1 < max1
{
if(m1 > max2)
max2 = m1 ;
}
}
return max2 ;
}
int main()
{
int arr[] = {5 , 6 ,8 , 3 , 7 ,9} ;
int m = max2(arr , 5) ;
cout<<m<<endl ;
getchar() ;
return 0 ;
}