时间戳

首页 > 解决方案 > 查找未排序数组的最小值和最大值的算法

algorithm - 查找未排序数组的最小值和最大值的算法

问题描述

首先，我想说这不是一个编码问题，而是一个算法问题。给定一个未排序的数组，我们如何有效地找到其中的最小和最大项？有很多例子可以找到最大值或最小值，但我有兴趣同时找到两者。一个简单的迭代比较方法不会有效，这是我的尝试，用一个例子直观地展示，也可以通过伪代码：

视觉示例

public static int[] findMinMax(int array[], int n, int m){
        int temp, mid;
        int[] left = new int[2]; // initialize new arrays with size 2 to store left and right side minmax values
        int[] right = new int[2];
        if (n <= m){ // Only 1 item is left in array
            int[] tempStorage = {array[n], array[n]};
            return tempStorage;
        }
        else if (n+1 == m){ // Only two items are in the array
            if (array[n] > array[m]){ // swap values if left value is bigger than right value
                temp = array[m];
                array[m] = array[n];
                array[n] = temp;
            }
        }
        mid = (n+m)/2; // find index of the midpoint in the array
        // Split the array into two recursively:
        left = findMinMax(array, n, mid);
        right = findMinMax(array, mid+1, m);

        //Compare the minimum values for left and right arrays, then assign the min to the first item in array
        if (left[n] < right[mid+1]){
            array[n] = left[n];
        }
        else{
            array[n] = right[mid+1];
        }
        //Compare the maximum values for left and right arrays, then assign the max to last item in array
        if (left[mid] > right[m]){
            array[m] = left[mid];
        }
        else{
            array[m] = right[m];
        }

    System.out.printf("Min: %d\nMax: %d\n", array[n], array[m]);
        return array;

所以我尝试将数组分成两部分，直到只剩下对；然后我比较它们并重新排列这对，使最小值在左边，最大值在右边。随后，我们向上移动并仅比较左右部分数组的最小值和最大值。在算法结束时，数组中的第一个值应该是最小值，最后一个值应该是最大值。我们并不真正关心介于两者之间的其他任何事情。

我不确定时间复杂度，但我认为应该是 O(n/2)？ 有没有其他方法可以以有效的时间复杂度做到这一点？我也想知道一些关于我提出的算法的反馈。谢谢你。

标签： algorithmminmax

解决方案

在少于 n - 1 次比较中无法在数组中找到最大/最小值，原因很清楚 - 您需要比较每个元素。

如果您看一下您的算法，实际上它需要进行 n - 1 次以上的比较，只需计算出现的红色数字的数量即可。但每个红色数字实际上对应不止1个比较。

推荐阅读