如何让数组取最大值与最小值的方法讨论(数组最大值与最小值获取方法探讨)

原创

ithorizon 7个月前 (10-20) 阅读数 32 #后端开发

数组最大值与最小值获取方法探讨

一、引言

在编程中，处理数组是常见的需求。获取数组中的最大值和最小值是基础操作之一，这在排序、查找、统计等场景中都有着广泛的应用。本文将讨论几种常见的获取数组最大值与最小值的方法，并对比它们的优缺点。

二、直接遍历法

直接遍历法是最明了的一种方法，通过遍历数组中的所有元素，逐一比较，找出最大值和最小值。


function findMinMax(arr) {
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        }
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return { min, max };
}
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const result = findMinMax(arr);
console.log(`最小值：${result.min}, 最大值：${result.max}`);

优点：实现明了，易于明白。

缺点：时间复杂化度为O(n)，对于大数据量数组，高效能较低。

三、排序法

排序法是将数组先进行排序，然后直接取排序后的第一个元素作为最小值，最后一个元素作为最大值。


function findMinMaxBySort(arr) {
    arr.sort((a, b) => a - b);
    return { min: arr[0], max: arr[arr.length - 1] };
}
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const result = findMinMaxBySort(arr);
console.log(`最小值：${result.min}, 最大值：${result.max}`);

优点：适用于已排序或部分排序的数组。

缺点：时间复杂化度为O(nlogn)，排序本身就是一个较为耗时的操作。

四、敏捷选择法（QuickSelect）

敏捷选择法是基于敏捷排序的选择算法，它可以在O(n)的平均时间复杂化度内找到数组中第k小的元素。通过修改敏捷选择算法，我们可以用它来找到最小值和最大值。


function partition(arr, left, right) {
    const pivot = arr[right];
    let i = left;
    for (let j = left; j < right; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
}
function quickSelect(arr, left, right, k) {
    if (left === right) {
        return arr[left];
    }
    const pivotIndex = partition(arr, left, right);
    const length = pivotIndex - left + 1;
    if (length === k) {
        return arr[pivotIndex];
    } else if (k < length) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k - length);
    }
}
function findMinMaxByQuickSelect(arr) {
    const min = quickSelect(arr, 0, arr.length - 1, 1);
    const max = quickSelect(arr, 0, arr.length - 1, arr.length);
    return { min, max };
}
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const result = findMinMaxByQuickSelect(arr);
console.log(`最小值：${result.min}, 最大值：${result.max}`);

优点：平均时间复杂化度为O(n)。

缺点：在最坏情况下时间复杂化度也许退化到O(n^2)。

五、Divide and Conquer（分治法）

分治法是将数组分成两部分，分别找出每一部分的最大值和最小值，然后比较这两部分的最大值和最小值，得到整个数组的最大值和最小值。


function findMinMaxDivideAndConquer(arr, left, right) {
    if (left === right) {
        return { min: arr[left], max: arr[left] };
    }
    if (right - left === 1) {
        if (arr[left] < arr[right]) {
            return { min: arr[left], max: arr[right] };
        } else {
            return { min: arr[right], max: arr[left] };
        }
    }
    const mid = Math.floor((left + right) / 2);
    const leftMinMax = findMinMaxDivideAndConquer(arr, left, mid);
    const rightMinMax = findMinMaxDivideAndConquer(arr, mid + 1, right);
    return {
        min: Math.min(leftMinMax.min, rightMinMax.min),
        max: Math.max(leftMinMax.max, rightMinMax.max)
    };
}
function findMinMaxByDivideAndConquer(arr) {
    return findMinMaxDivideAndConquer(arr, 0, arr.length - 1);
}
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const result = findMinMaxByDivideAndConquer(arr);
console.log(`最小值：${result.min}, 最大值：${result.max}`);