笙亿网络策划

数据结构与算法中 Max-Min Problem 怎么解决？

约 18 分钟读完 34 阅
文章导读
上一个 测验 下一个 让我们考虑一个可以使用分治技术解决的简单问题。
📋 目录
  1. 壹 最大-最小问题
  2. 贰 朴素方法
  3. 叁 分治法
A A

最大-最小问题

目录
  • 最大-最小问题
  • 朴素方法
  • 分治法
上一个
测验
下一个

让我们考虑一个可以使用分治技术解决的简单问题。

最大-最小问题

算法分析中的最大-最小问题是在数组中找到最大值和最小值。

解决方案

要在给定数组 numbers[]（大小为 n）中找到最大和最小数，可以使用以下算法。首先我们介绍朴素方法，然后呈现分治法。

朴素方法

朴素方法是一种解决任意问题的基本方法。在这种方法中，可以分别找到最大值和最小值。要找到最大值和最小值，可以使用以下直观的算法。

算法：Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

示例

以下是上述方法在各种编程语言中的实现 −

C C++ Java Python 
#include <stdio.h>
struct Pair {
    int max;
    int min;
};
// 使用朴素算法查找最大值和最小值的函数
struct Pair maxMinNaive(int arr[], int n) {
    struct Pair result;
    result.max = arr[0];
    result.min = arr[0];
    // 遍历数组以找到最大值和最小值
    for (int i = 1; i < n; i++) {
        if (arr[i] > result.max) {
            result.max = arr[i]; // 如果找到更大的元素，则更新最大值
        }
        if (arr[i] < result.min) {
            result.min = arr[i]; // 如果找到更小的元素，则更新最小值
        }
    }
    return result; // 返回最大值和最小值的对
}
int main() {
    int arr[] = {6, 4, 26, 14, 33, 64, 46};
    int n = sizeof(arr) / sizeof(arr[0]);
    struct Pair result = maxMinNaive(arr, n);
    printf("Maximum element is: %d\n", result.max);
    printf("Minimum element is: %d\n", result.min);
    return 0;
}

输出

Maximum element is: 64
Minimum element is: 4

#include <iostream>
using namespace std;
struct Pair {
    int max;
    int min;
};
// 使用朴素算法查找最大值和最小值的函数
Pair maxMinNaive(int arr[], int n) {
    Pair result;
    result.max = arr[0];
    result.min = arr[0];
    // 遍历数组以找到最大值和最小值
    for (int i = 1; i < n; i++) {
        if (arr[i] > result.max) {
            result.max = arr[i]; // 如果找到更大的元素，则更新最大值
        }
        if (arr[i] < result.min) {
            result.min = arr[i]; // 如果找到更小的元素，则更新最小值
        }
    }
    return result; // 返回最大值和最小值的对
}
int main() {
    int arr[] = {6, 4, 26, 14, 33, 64, 46};
    int n = sizeof(arr) / sizeof(arr[0]);
    Pair result = maxMinNaive(arr, n);
    cout << "Maximum element is: " << result.max << endl;
    cout << "Minimum element is: " << result.min << endl;
    return 0;
}

输出

Maximum element is: 64
Minimum element is: 4

public class MaxMinNaive {
    static class Pair {
        int max;
        int min;
    }
    // 使用朴素算法查找最大值和最小值的函数
    static Pair maxMinNaive(int[] arr) {
        Pair result = new Pair();
        result.max = arr[0];
        result.min = arr[0];
        // 遍历数组以找到最大值和最小值
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > result.max) {
                result.max = arr[i]; // 如果找到更大的元素，则更新最大值
            }
            if (arr[i] < result.min) {
                result.min = arr[i]; // 如果找到更小的元素，则更新最小值
            }
        }
        return result; // 返回最大值和最小值的对
    }
    public static void main(String[] args) {
        int[] arr = {6, 4, 26, 14, 33, 64, 46};
        Pair result = maxMinNaive(arr);
        System.out.println("Maximum element is: " + result.max);
        System.out.println("Minimum element is: " + result.min);
    }
}

输出

Maximum element is: 64
Minimum element is: 4

def max_min_naive(arr):
    max_val = arr[0]
    min_val = arr[0]
    # 遍历数组以找到最大值和最小值
    for i in range(1, len(arr)):
        if arr[i] > max_val:
            max_val = arr[i]  # 如果找到更大的元素，则更新最大值
        if arr[i] < min_val:
            min_val = arr[i]  # 如果找到更小的元素，则更新最小值
    return max_val, min_val  # 返回最大值和最小值的对
arr = [6, 4, 26, 14, 33, 64, 46]
max_val, min_val = max_min_naive(arr)
print("Maximum element is:", max_val)
print("Minimum element is:", min_val)

输出

Maximum element is: 64
Minimum element is: 4

分析

朴素方法的比较次数为 2n - 2。

使用分治法可以减少比较次数。以下是该技术。

分治法

在这种方法中，将数组分为两半。然后使用递归方法找到每半部分的最大值和最小值。随后，返回两半部分最大值中的最大值以及两半部分最小值中的最小值。

在该问题中，数组中的元素个数为 $y - x + 1$，其中 y 大于或等于 x。

$\mathbf{\mathit{Max - Min(x, y)}}$ 将返回数组 $\mathbf{\mathit{numbers[x...y]}}$ 的最大值和最小值。

算法：Max - Min(x, y) 
if y  x ≤ 1 then  
   return (max(numbers[x],numbers[y]),min((numbers[x],numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

示例

以下是上述方法在各种编程语言中的实现 −

C C++ Java Python 
#include <stdio.h>
// 用于存储最大值和最小值的结构体
struct Pair {
    int max;
    int min;
};
struct Pair maxMinDivideConquer(int arr[], int low, int high) {
    struct Pair result;
    struct Pair left;
    struct Pair right;
    int mid;
    // 如果数组中只有一个元素
    if (low == high) {
        result.max = arr[low];
        result.min = arr[low];
        return result;
    }
    // 如果数组中有两个元素
    if (high == low + 1) {
        if (arr[low] < arr[high]) {
            result.min = arr[low];
            result.max = arr[high];
        } else {
            result.min = arr[high];
            result.max = arr[low];
        }
        return result;
    }
    // 如果数组中有超过两个元素
    mid = (low + high) / 2;
    left = maxMinDivideConquer(arr, low, mid);
    right = maxMinDivideConquer(arr, mid + 1, high);
    // 比较并获取两部分的最大值
    result.max = (left.max > right.max) ? left.max : right.max;
    // 比较并获取两部分的最小值
    result.min = (left.min < right.min) ? left.min : right.min;
    return result;
}
int main() {
    int arr[] = {6, 4, 26, 14, 33, 64, 46};
    int n = sizeof(arr) / sizeof(arr[0]);
    struct Pair result = maxMinDivideConquer(arr, 0, n - 1);
    printf("Maximum element is: %d\n", result.max);
    printf("Minimum element is: %d\n", result.min);
    return 0;
}

输出

Maximum element is: 64
Minimum element is: 4

#include <iostream>
using namespace std;
// 用于存储最大值和最小值的结构体
struct Pair {
    int max;
    int min;
};
Pair maxMinDivideConquer(int arr[], int low, int high) {
    Pair result, left, right;
    int mid;
    // 如果数组中只有一个元素
    if (low == high) {
        result.max = arr[low];
        result.min = arr[low];
        return result;
    }
    // 如果数组中有两个元素
    if (high == low + 1) {
        if (arr[low] < arr[high]) {
            result.min = arr[low];
            result.max = arr[high];
        } else {
            result.min = arr[high];
            result.max = arr[low];
        }
        return result;
    }
    // 如果数组中有超过两个元素
    mid = (low + high) / 2;
    left = maxMinDivideConquer(arr, low, mid);
    right = maxMinDivideConquer(arr, mid + 1, high);
    // 比较并获取两部分的最大值
    result.max = (left.max > right.max) ? left.max : right.max;
    // 比较并获取两部分的最小值
    result.min = (left.min < right.min) ? left.min : right.min;
    return result;
}
int main() {
    int arr[] = {6, 4, 26, 14, 33, 64, 46};
    int n = sizeof(arr) / sizeof(arr[0]);
    Pair result = maxMinDivideConquer(arr, 0, n - 1);
    cout << "Maximum element is: " << result.max << endl;
    cout << "Minimum element is: " << result.min << endl;
    return 0;
}

输出

Maximum element is: 64
Minimum element is: 4 

public class MaxMinDivideConquer {
    // 用于存储最大值和最小值的类
    static class Pair {
        int max;
        int min;
    }
    static Pair maxMinDivideConquer(int[] arr, int low, int high) {
        Pair result = new Pair();
        Pair left, right;
        int mid;
        // 如果数组中只有一个元素
        if (low == high) {
            result.max = arr[low];
            result.min = arr[low];
            return result;
        }
        // 如果数组中有两个元素
        if (high == low + 1) {
            if (arr[low] < arr[high]) {
                result.min = arr[low];
                result.max = arr[high];
            } else {
                result.min = arr[high];
                result.max = arr[low];
            }
            return result;
        }
        // 如果数组中有超过两个元素
        mid = (low + high) / 2;
        left = maxMinDivideConquer(arr, low, mid);
        right = maxMinDivideConquer(arr, mid + 1, high);
        // 比较并获取两部分的最大值
        result.max = Math.max(left.max, right.max);
        // 比较并获取两部分的最小值
        result.min = Math.min(left.min, right.min);
        return result;
    }
    public static void main(String[] args) {
        int[] arr = {6, 4, 26, 14, 33, 64, 46};
        Pair result = maxMinDivideConquer(arr, 0, arr.length - 1);
        System.out.println("Maximum element is: " + result.max);
        System.out.println("Minimum element is: " + result.min);
    }
}

输出

Maximum element is: 64
Minimum element is: 4

def max_min_divide_conquer(arr, low, high):
    # 用于存储最大值和最小值的结构
    class Pair:
        def __init__(self):
            self.max = 0
            self.min = 0
    result = Pair()
    # 如果数组中只有一个元素
    if low == high:
        result.max = arr[low]
        result.min = arr[low]
        return result
    # 如果数组中有两个元素
    if high == low + 1:
        if arr[low] < arr[high]:
            result.min = arr[low]
            result.max = arr[high]
        else:
            result.min = arr[high]
            result.max = arr[low]
        return result
    # 如果数组中有超过两个元素
    mid = (low + high) // 2
    left = max_min_divide_conquer(arr, low, mid)
    right = max_min_divide_conquer(arr, mid + 1, high)
    # 比较并获取两部分的最大值
    result.max = max(left.max, right.max)
    # 比较并获取两部分的最小值
    result.min = min(left.min, right.min)
    return result
arr = [6, 4, 26, 14, 33, 64, 46]
result = max_min_divide_conquer(arr, 0, len(arr) - 1)
print("Maximum element is:", result.max)
print("Minimum element is:", result.min)

输出

Maximum element is: 64
Minimum element is: 4

分析

设 T(n) 表示 $\mathbf{\mathit{Max - Min(x, y)}}$ 所进行的比较次数，其中元素个数 $n = y - x + 1$。

如果 T(n) 表示比较次数，则递推关系可以表示为

$$T(n) = \begin{cases}T\left(\lfloor\frac{n}{2}\rfloor\right)+T\left(\lceil\frac{n}{2}\rceil\right)+2 & for\: n>2\\1 & for\:n = 2 \\0 & for\:n = 1\end{cases}$$

假设 n 是 2 的幂形式。因此，n = 2k，其中 k 是递归树的高度。

因此，

$$T(n) = 2.T (\frac{n}{2}) + 2 = 2.\left(\begin{array}{c}2.T(\frac{n}{4}) + 2\end{array}\right) + 2 ..... = \frac{3n}{2} - 2$$

与朴素方法相比，分治法中的比较次数更少。然而，使用渐近记号表示，两种方法的复杂度均为 O(n)。