2.10 用最少次数寻找数组中的最大值和最小值[find min max of array]

妖刀路过

【题目】

对于一个由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 a[j]         getMinMax(a, 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; }