从数组中获取最小值或最大值的最佳方法是什么？

假设我有一个数字数组: [2,3,3,4,2,2,5,6,7,2]

找到该数组中最小值或最大值的最佳方法是什么？

现在,为了获得最大值,我循环遍历数组,并将变量重置为该值,如果它大于现有值:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

var maxValue:Number = 0;

for each (var num:Number in myArray)
{
    if (num > maxValue)
        maxValue = num;
}

这似乎不是执行此操作的最佳方式(我尽可能避免循环).

其他人的理论答案都很整洁,但让我们务实.ActionScript提供了您需要的工具,因此在这种情况下您甚至不必编写循环!

首先,请注意Math.min()并且Math.max()可以采用任意数量的参数.此外,了解对象apply()可用的方法也很重要Function.它允许您使用a将参数传递给函数Array.让我们利用两者:

var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);

这是最好的部分:"循环"实际上是使用本机代码(在Flash Player内部)运行的,因此它比使用纯ActionScript循环搜索最小值或最大值更快.

在没有测试每个值的情况下,没有任何可靠的方法来获得最小值/最大值.你不想尝试排序或类似的东西,遍历数组是O(n),这比任何排序算法在一般情况下都能做的要好.

如果

数组未排序

找到最小值和最大值同时完成

然后有一个算法可以找到3n/2个比较中的最小值和最大值.我们需要做的是成对处理数组的元素.应将该对中较大的一对与当前最大值进行比较,并将该对中较小的一对与当前最小值进行比较.此外,如果数组包含奇数个元素,则需要特别小心.

在c ++代码中(从Mehrdad借用一些代码).

struct MinMax{
   int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   MinMax  min_max;
   int index;
   int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
   if ( n%2 != 0 ){// if n is odd

     min_max.Min = array[start];
     min_max.Max = array[start];

     index = start + 1;
   }
   else{// n is even
     if ( array[start] < array[start+1] ){
       min_max.Min = array[start];
       min_max.Max = array[start+1];
     }
     else{
       min_max.Min = array[start+1];
       min_max.Max = array[start];
     }
     index = start + 2;
   }

   int big, small;
   for ( int i = index; i < n-1; i = i+2 ){
      if ( array[i] < array[i+1] ){ //one comparison
        small = array[i];
        big = array[i+1];
      }
      else{
        small = array[i+1];
        big = array[i];
      }
      if ( min_max.Min > small ){ //one comparison
        min_max.Min = small;
      }
      if ( min_max.Max < big ){ //one comparison
        min_max.Max = big;
      }
   }

   return min_max;
}

很容易看出它所需的比较次数是3n/2.循环运行n/2次,并且在每次迭代中执行3次比较.这可能是最佳的.在这一刻,我无法指出这一点.(但是,我想我已经在某处看到过这方面的证据.)

Mehrdad上面给出的递归解决方案可能也实现了这种最小数量的比较(最后一行需要改变).但是,通过相同数量的比较,迭代解决方案将始终击败递归解决方案,因为他提到了函数调用的开销.然而,如果只关心找到一些数字的最小值和最大值(正如Eric Belair所做的那样),没有人会注意到今天的计算机与上述任何方法有任何区别.对于大型阵列,差异可能很大.

虽然这个解决方案和Matthew Brubaker给出的解决方案具有O(n)复杂性,但在实践中应该仔细评估所涉及的隐藏常数.他的解决方案中的比较次数是2n.与2n比较相比,使用3n/2比较的解决方案获得的加速将是显而易见的.

除非对数组进行排序,否则这将是您获得的最佳选择.如果它已排序,只需获取第一个和最后一个元素.

当然,如果它没有排序,那么首先排序并抓住第一个和最后一个保证效率低于仅循环一次.即使是最好的排序算法也必须多次查看每个元素(每个元素的平均O(log N)次.这就是O(N*Log N)总数.一次扫描的简单只是O(N).

如果您想快速访问数据结构中的最大元素,请查看堆,以便以某种顺序保持对象的有效方法.

你必须遍历数组,没有其他方法来检查所有元素.只需对代码进行一次校正 - 如果所有元素都为负数,则maxValue最后为0.您应该使用整数的最小可能值对其进行初始化.
如果你要多次搜索数组,最好先对它进行排序,而不是搜索更快(二进制搜索),最小和最大元素只是第一个和最后一个.