尋找數(shù)組中的最大值和最小值
一 問(wèn)題描述
試著用最小的比較次數(shù)去尋找數(shù)組中的最大值和最小值。
方法1：
分別遍歷兩次數(shù)組，分別求取數(shù)組中的最大值和最小值。這樣其比較次數(shù)為2*N
方法2：
首先內(nèi)存中維持兩個(gè)變量，max 和 min 。
將數(shù)組中相鄰的兩個(gè)元素兩兩配對(duì)，對(duì)沒(méi)對(duì)數(shù)據(jù)進(jìn)行比較，并將數(shù)據(jù)對(duì)中的較大值和max比較，
將較小值跟min進(jìn)行比較。此時(shí) 比較的次數(shù)為1.5 * n 。
方法3：
利用分治方法，類似歸并排序。
逐次將數(shù)組分成兩部分，然后比較兩部分的最大值和最小值。
代碼如下：
#include <iostream>
using namespace std ;
/**//*
利用分治法求一個(gè)數(shù)組的最大最小值
其比較次數(shù)仍然為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 ;
}
二 求取數(shù)組中的第二大數(shù)字
也可以兩兩結(jié)合，比較的次數(shù)也為1.5N ，但是無(wú)法使用分治方法解決。代碼如下：
/**//*
求取數(shù)組中的第二大的數(shù)字 , 也可以兩兩比較
但是不能使用分治法
*/
#include <iostream>
using namespace std ;
int max2(int * arr , int n)
{
if(!arr || !n )
return -1;
int begin ;
int max1 , max2; //存儲(chǔ)最大值和最小值
if(n & 1) //奇數(shù)
{
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 ;
}