作者:mobiledu2502906557 | 来源:互联网 | 2023-10-10 19:15
【本文链接】
http://www.cnblogs.com/hellogiser/p/find-min-max-of-array.html
【题目】
对于一个由N个整数组成的数组,需要比较多少次才能把最大和最小的数找出来呢?
【分析】
1. 遍历两次数组,分别找出最大值和最小值,需要进行 2N 次比较。
2. 将数组中的元素分组,按顺序将数组中相邻的两个数分在同一组,用Max和Min来存储最大值和最小值。同一组比较完之后,较小的数与当前的最小值比较,如该数小于当前最小值,更新Min;较大的数与当前的最大值比较,若该数大于当前最大值,更新Max。Max初始化为数组前两个数中较大值,Min初始化为数组前两个组中较小值。这种方法的比较次数是(N/2)*3=1.5N次。
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
|
|
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/7/10
*/
void getMinMax(int a, int b, int *min, int *max)
{
// compare 1 time
if(a > b)
{
*min = b;
*max = a;
}
else
{
*min = a;
*max = b;
}
}
void findArrMinMax(int a[], int size, int *min, int *max)
{
if(size == 0)
return;
if(size == 1)
{
*min = *max = a[0];
return;
}
// get min max of a[0] a[1]
getMinMax(a[0], a[1], min, max);
int i, j;
int *tempmin, *tempmax;
for(i = 2, j = 3; i < size, j < size; i += 2, j += 2)
{
// get min max of a[i] a[j]
getMinMax(a[i], a[j], tempmin, tempmax);
if(*tempmax > *max)
*max = *tempmax;
if(*tempmin < *min)
*min = *tempmin;
}
// if array size is odd, then the last element a[size-1] is not contained in previous steps,so compare here
if(size % 2 != 0)
{
if(a[size - 1] > *max)
*max = a[size - 1];
else if(a[size - 1] < *min)
*min = a[size - 1];
}
}
|
3. 使用分治法,在N个数中求最小值Min和最大值Max,我们只需要求出前后N/2个数的Min和Max,然后取较小的Min和较大的Max即可。设比较的次数为T(n),那么T(n)=2T(n/2)+2,T(1)=0,T(2)=1,这种方法的比较次数是1.5N-2次。
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
|
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/7/10
*/
void findArrMinMax(int a[], int begin, int end, int *min, int *max)
{
if(end - begin <= 1)
{
if(a[end] > a[begin])
{
*max = a[end];
*min = a[begin];
}
else
{
*max = a[begin];
*min = a[end];
}
return;
}
int maxL, maxR;
int minL, minR;
int mid = begin + (end - begin) / 2;
findArrMinMax(a, begin, mid, &minL, &maxL);
findArrMinMax(a, mid + 1, end, &minR, &maxR);
*min = minL > minR ? minR : minL;
*max = maxL > maxR ? maxL : maxR;
}
|
【参考】
http://blog.csdn.net/caryaliu/article/details/8135898
http://www.cnblogs.com/lovell-liu/archive/2011/09/07/2169644.html
【本文链接】
http://www.cnblogs.com/hellogiser/p/find-min-max-of-array.html
2.10 用最少次数寻找数组中的最大值和最小值[find min max of array],,
2.10 用最少次数寻找数组中的最大值和最小值[find min max of array]