寻找数组中的最大值和最小值

问题来源：《编程之美》2.10 寻找数组中的最大值和最小值

对于一个由N个整数组成的数组，需要比较多少次才能把最大和最小的数找出来呢？

1. 遍历两次数组，分别找出最大值和最小值。需要进行 2 * N 次比较

2. 将数组中的元素分组，按顺序将数组中相邻的两个数分在同一组，用Max和Min来存储最大值和最小值，同一组比较完之后，较小的数与当前的最小值比较，如该数小于当前最小值，更新Min，较大的数与当前的最大值比较，若该数大于当前最大值，更新Max。Max初始化为数组前两个数中较大值，Min初始化为数组前两个组中较小值。

这样方法未破坏原数组，比较次数是1.5N次，程序描述如下：

void findArrMaxMin(int a[], int size, int *min, int *max)
{
    if(size == 0) {
        return;
    }
    if(size == 1) {
        *min = *max = a[0];
        return;
    }

    *min = a[0] > a[1] ? a[1] : a[0];
    *max = a[0] <= a[1] ? a[1] : a[0];


    int i, j;
    for(i = 2, j = 3; i < size, j < size; i += 2, j += 2) {
        int tempmax = a[i] >= a[j] ? a[i] : a[j];
        int tempmin = a[i] < a[j] ? a[i] : a[j];

        if(tempmax > *max)
            *max = tempmax;
        if(tempmin < *min)
            *min = tempmin;
    }

    //如果数组元素是奇数个，那么最后一个元素在分组的过程中没有包含其中，
    //这里单独比较
    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即可。这种方法比较的次数是1.5N次，程序描述如下：

void arrMaxMin(int a[], int begin, int end, int *max, int *min)
{
    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;
    arrMaxMin(a, begin, begin + (end - begin)/2, &maxL, &minL);
    arrMaxMin(a, begin + (end - begin)/2 + 1, end, &maxR, &minR);
    *max = maxL > maxR ? maxL : maxR;
    *min = minL > minR ? minR : minL;
}

程序测试代码如下：

#include <stdlib.h>
#include <stdio.h>

void findArrMaxMin(int a[], int size, int *min, int *max)
{
    if(size == 0) {
        return;
    }
    if(size == 1) {
        *min = *max = a[0];
        return;
    }

    *min = a[0] > a[1] ? a[1] : a[0];
    *max = a[0] <= a[1] ? a[1] : a[0];


    int i, j;
    for(i = 2, j = 3; i < size, j < size; i += 2, j += 2) {
        int tempmax = a[i] >= a[j] ? a[i] : a[j];
        int tempmin = a[i] < a[j] ? a[i] : a[j];

        if(tempmax > *max)
            *max = tempmax;
        if(tempmin < *min)
            *min = tempmin;
    }

    //如果数组元素是奇数个，那么最后一个元素在分组的过程中没有包含其中，
    //这里单独比较
    if(size % 2 != 0) {
        if(a[size -1] > *max)
            *max = a[size - 1];
        else if(a[size -1] < *min)
            *min = a[size -1];
    }
}

void arrMaxMin(int a[], int begin, int end, int *max, int *min)
{
    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;
    arrMaxMin(a, begin, begin + (end - begin)/2, &maxL, &minL);
    arrMaxMin(a, begin + (end - begin)/2 + 1, end, &maxR, &minR);
    *max = maxL > maxR ? maxL : maxR;
    *min = minL > minR ? minR : minL;
}
int main()
{
    int a[] = {3, 2, 56, 109, 10, 95, 1, 230, -1000};
    int n = sizeof(a)/sizeof(int);
    int min, max;
    findArrMaxMin(a, n, &min, &max);
    printf("min = %d, max = %d\n", min, max);
    arrMaxMin(a, 0, n - 1, &max, &min);
    printf("min = %d, max = %d\n", min, max);
}

我的微博：http://weibo.com/caryaliu

个人新博客，欢迎关注：http://readus.org