如何在数组中查找最大值和最小值？

在数组中查找最大值和最小值是常见的数据处理操作。以下是几种常见的方法来实现这一目标：

方法一：遍历比较法

这是最直接的方法之一。我们通过遍历数组中的每个元素，依次与当前的最大值和最小值进行比较。

首先，初始化最大值和最小值为数组的第一个元素。然后，从第二个元素开始遍历数组，对于每个元素，将其与当前最大值和最小值进行比较。如果元素大于最大值，则更新最大值；如果元素小于最小值，则更新最小值。

这种方法的时间复杂度为$O(n)$，其中$n$是数组的长度，因为需要遍历整个数组。

以下是使用这种方法的示例代码（以 Java 为例）：

public class FindMaxMin {
   
    public static void main(String[] args) {
   
        int[] array = {
   12, 5, 8, 20, 3, 15};

        int max = array[0];
        int min = array[0];

        for (int i = 1; i < array.length; i++) {
   
            int element = array[i];

            if (element > max) {
   
                max = element;
            } else if (element < min) {
   
                min = element;
            }
        }

        System.out.println("最大值：" + max);
        System.out.println("最小值：" + min);
    }
}

方法二：排序后取首尾元素法

我们可以先对数组进行排序，然后数组的第一个元素就是最小值，最后一个元素就是最大值。

这种方法的时间复杂度主要取决于所使用的排序算法。常见的排序算法如冒泡排序、插入排序、选择排序等的时间复杂度通常为$O(n^2)$，快速排序等高效排序算法的时间复杂度可以达到$O(n\log n)$。

以下是使用这种方法的示例代码（以 Java 为例，使用快速排序进行排序）：

import java.util.Arrays;

public class FindMaxMinBySorting {
   
    public static void main(String[] args) {
   
        int[] array = {
   12, 5, 8, 20, 3, 15};

        Arrays.sort(array);

        int min = array[0];
        int max = array[array.length - 1];

        System.out.println("最大值：" + max);
        System.out.println("最小值：" + min);
    }
}

方法三：分治法

分治法是一种将问题分解成子问题并分别解决的策略。对于查找数组中的最大值和最小值，我们可以将数组分成两部分，分别在两部分中找出最大值和最小值，然后再在这两个结果中找出全局的最大值和最小值。

这种方法的时间复杂度也是$O(n)$。

以下是使用分治法的示例代码（以 Java 为例）：

public class FindMaxMinByDivideAndConquer {
   
    public static void main(String[] args) {
   
        int[] array = {
   12, 5, 8, 20, 3, 15};

        int[] result = findMaxAndMin(array, 0, array.length - 1);

        System.out.println("最大值：" + result[0]);
        System.out.println("最小值：" + result[1]);
    }

    public static int[] findMaxAndMin(int[] array, int start, int end) {
   
        if (start == end) {
   
            return new int[]{
   array[start], array[start]};
        }

        int mid = (start + end) / 2;

        int[] leftResult = findMaxAndMin(array, start, mid);
        int[] rightResult = findMaxAndMin(array, mid + 1, end);

        int max = Math.max(leftResult[0], rightResult[0]);
        int min = Math.min(leftResult[1], rightResult[1]);

        return new int[]{
   max, min};
    }
}

综上所述，我们可以根据具体的需求和情况选择合适的方法来查找数组中的最大值和最小值。这些方法各有优缺点，在实际应用中需要根据数据的特点和性能要求进行权衡和选择。