工学1号馆

home

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

Wu Yudong    July 23, 2016     Algorithm   699   

数组是最简单的一种数据结构。我们经常碰到的一个基本问题,就是寻找整个数组中最大的数,或者最小的数。这时,我们都会扫描一遍数组,把最大(最小)的数找出来。如果我们需要同时找出最大和最小的数呢?

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

本文地址:http://wuyudong.com/2016/07/23/2261.html,转载请注明源地址。

解法一:分别求最大和最小值

可以分别求出数组的最大值和最小值,这样,我们需要比较2N次才能求解。

void find_max_min1(int a[], int size, int *min, int *max)
{
    int i;
    *min = *max = a[0];
    for (i = 1; i < size; i++) {
        if (a[i] > *max)
            *max = a[i];
        if (a[i] < *min)
            *min = a[i];
    }
}

解法二:分组求解

(1) 按顺序将数组中相邻的两个数分在同一组;

(2) 比较同一组的两个数,将大的数放在偶数位上,小的放在奇数位上;

(3) 最后,从偶数位上求最大值,奇数位上求最小值即可。

一共需要比较1.5N次。这种办法虽然比较次数变少了,但却破坏了原数组。

void swap(int *a, int *b)
{
    int p;
    p = *a;
    *a = *b;
    *b = p;
}
void find_max_min2(int a[], int size, int *min, int *max)
{
    int i, t;
    *min = *max = a[0];
    t = (size % 2) ? (size - 2) : (size - 1);
    for (i = 0; i <= t; i += 2) {
        if (a[i] > a[i + 1])
            swap(&a[i], &a[i + 1]);
    }
    for (i = 0; i <= t; i += 2) {
        if (*max < a[i + 1])
            *max = a[i + 1];
        if (*min > a[i])
            *min = a[i];
    }
    if (size % 2) {
        if (*min > a[size - 1])
            *min = a[size - 1];
        else if (*max < a[size - 1])
            *max = a[size - 1];
    }
}

解法三:改进的分组

(1) 用两个变量max和min分别存储当前的最大值和最小值。

(2) 同一组的两个数比较完之后,不再调整顺序,将其中较大的与当前max比较,较小的与min比较;

(3) 如此反复,直到遍历完整个数组。

整个过程比较次数为1.5N次。

void find_max_min3(int a[], int size, int *min, int *max)
{
    int i, t;
    *min = *max = a[0];
    t = (size % 2) ? (size - 2) : (size - 1);
    for (i = 0; i <= t; i += 2) {
        if (a[i] > a[i + 1]) {
            if (*min > a[i + 1]) {
                *min = a[i + 1];
            }
            if (*max < a[i]) {
                *max = a[i];
            }
        } else {
            if (*min > a[i]) {
                *min = a[i];
            }
            if (*max < a[i + 1]) {
                *max = a[i + 1];
            }
        }

    }
    if (size % 2) {
        if (*min > a[size - 1])
            *min = a[size - 1];
        else if (*max < a[size - 1])
            *max = a[size - 1];
    }
}

解法四:分治策略

分别求出前后N/2个数的min和max,然后,取较小的min,较大的max即可。

需要比较的次数为1.5N-2,分析略。

void _find_max_min4(const int arr[], size_t low, size_t high, int *min_value, int *max_value)
{
    if (high - low <= 1u) {
        if (arr[low] <= arr[high]) {
            *min_value = arr[low];
            *max_value = arr[high];
        } else {
            *min_value = arr[high];
            *max_value = arr[low];
        }
        return;
    }

    size_t mid = low + (high - low) / 2u;
    int min_left, max_left;
    _find_max_min4(arr, low, mid, &min_left, &max_left);

    int min_right, max_right;
    _find_max_min4(arr, mid + 1, high, &min_right, &max_right);

    *min_value = min_left < min_right ? min_left : min_right;
    *max_value = max_left > max_right ? max_left : max_right;
}

void find_max_min4(const int arr[], const size_t len, int *min_value, int *max_value)
{
    _find_max_min4(arr, 0, len - 1u, min_value, max_value);
}

 

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)