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

Let's say I have an Array of numbers: [2,3,3,4,2,2,5,6,7,2]

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

What is the best way to find the minimum or maximum value in that Array?

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

Right now, to get the maximum, I am looping through the Array, and resetting a variable to the value if it is greater than the existing value:

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

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;
}

This just doesn't seem like the best performing way to do this (I try to avoid loops whenever possible).

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

18 个解决方案

#1

The theoretical answers from everyone else are all neat, but let's be pragmatic. ActionScript provides the tools you need so that you don't even have to write a loop in this case!

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

First, note that Math.min() and Math.max() can take any number of arguments. Also, it's important to understand the apply() method available to Function objects. It allows you to pass arguments to the function using an Array. Let's take advantage of both:

首先,请注意Math.min()和Math.max()可以使用任意数量的参数。另外,理解Function对象可用的apply()方法很重要。它允许您使用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);

Here's the best part: the "loop" is actually run using native code (inside Flash Player), so it's faster than searching for the minimum or maximum value using a pure ActionScript loop.

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

#2

There isn't any reliable way to get the minimum/maximum without testing every value. You don't want to try a sort or anything like that, walking through the array is O(n), which is better than any sort algorithm can do in the general case.

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

#3

If

1. The array is not sorted

数组未排序

2. Finding the min and max is done simultaneously

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

Then there is an algorithm that finds the min and max in 3n/2 number of comparisons. What one needs to do is process the elements of the array in pairs. The larger of the pair should be compared with the current max and the smaller of the pair should be compared with the current min. Also, one needs take special care if the array contains odd number of elements.

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

In c++ code (borrowing some code from Mehrdad).

在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;
}

It's very easy to see that the number of comparisons it takes is 3n/2. The loop runs n/2 times and in each iteration 3 comparisons are performed. This is probably the optimum one can achieve. At this moment, I cannot point to a definite source of that. (But, I think I have seen a proof of that somewhere.)

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

The recursive solution given by Mehrdad above, probably also achieves this minimal number of comparisons (the last line needs to be changed). But with the same number of comparisons an iterative solution will always beat a recursive solution due to overhead in the function call as he mentioned. However, if one only cares about finding min and max of a few numbers (as Eric Belair does), no one will notice any difference in todays computer with any of the approaches above. For a large array, the difference could be significant.

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

Though this solution and the solution given by Matthew Brubaker has O(n) complexity, in practice one should carefully asses the hidden constants involved. The number of comparisons in his solution is 2n. The speedup gained with the solution with 3n/2 comparisons as opposed to 2n comparisons would be noticeable.

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

#4

Unless the array is sorted, that's the best you're going to get. If it is sorted, just take the first and last elements.

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

Of course, if it's not sorted, then sorting first and grabbing the first and last is guaranteed to be less efficient than just looping through once. Even the best sorting algorithms have to look at each element more than once (an average of O(log N) times for each element. That's O(N*Log N) total. A simple scan once through is only O(N).

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

If you are wanting quick access to the largest element in a data structure, take a look at heaps for an efficient way to keep objects in some sort of order.

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

#5

You have to loop through the array, no other way to check all elements. Just one correction for the code - if all elements are negative, maxValue will be 0 at the end. You should initialize it with the minimum possible value for integer.
And if you are going to search the array many times it's a good idea to sort it first, than searching is faster (binary search) and minimum and maximum elements are just the first and the last.

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

#6

Depends on what you call "best." From a theoretical point of view, you cannot solve the problem in less than O(n) in a deterministic Turing machine.

取决于你所谓的“最好”。从理论的角度来看,在确定性图灵机中,你不能在小于O(n)的情况下解决问题。

The naive algorithm is too loop and update min, max. However, a recursive solution will require less comparisons than naive algorithm, if you want to get min, max simultaneously (it isn't necessarily faster due to function call overhead).

朴素算法太循环并且更新min,max。但是,如果要同时获得最小值,最大值(由于函数调用开销,它不一定更快),递归解决方案将需要比天真算法更少的比较。

struct MinMax{
   public int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   if (start == end)
      return new MinMax { Min = array[start], Max = array[start] };

   if (start == end - 1)
      return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;

   MinMax res1 = FindMinMax(array, start, (start + end)/2);
   MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
   return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}

The simplest solution would be to sort and get the first and last item, though it's obviously not the fastest ;)

最简单的解决方案是排序并获取第一个和最后一个项目,尽管它显然不是最快的;)

The best solution, performance-wise, to find the minimum or maximum is the naive algorithm you written (with a single loop).

在性能方面,找到最小值或最大值的最佳解决方案是您编写的简单算法(使用单个循环)。

#7

Math.max() is actually as3 code compiled to AVM2 opcodes, and as such is not more "native" than any other as3 code. As a consequence, it is not necessarily the fastest implementation.

Math.max()实际上是编译为AVM2操作码的as3代码,因此不比任何其他as3代码更“本机”。因此,它不一定是最快的实施。

Actually, given that it works on Array type, it is slower than carefully written code usign Vector:

实际上,鉴于它适用于Array类型,它比精心编写的代码usign Vector慢:

I did a quick benchmark comparison of several naive Vector and Array implementations of Math.max, using gskinner's PerformanceTest (Vector and Array being filled with identical random Numbers). The fastest Vector implementation appeared to be more than 3x faster than Math.max with recent AIR SDK/release player (flash player WIN 14,0,0,122 RELEASE, compiled with AIR SDK 14):

我使用gskinner的PerformanceTest(Vector和Array填充相同的随机数)对Math.max的几个天真的Vector和Array实现进行了快速基准比较。使用最新的AIR SDK /发布播放器(使用AIR SDK 14编译的Flash播放器WIN 14,0,0,122 RELEASE),最快的Vector实现似乎比Math.max快3倍以上:

average 3.5 ms for 1,000,000 values, compared to Math.max() average of 11ms :

1,000,000个值的平均值为3.5 ms,而Math.max()的平均值为11 ms:

function max(values:Vector.<Number>):Number
{
    var max:Number = Number.MIN_VALUE;
    var length:uint = values.length;
    for (var i:uint = 0; i < length ; ++i)
        if (values[i] > max)
            max = values[i];
    return max;
}

Conclusion is that if you are concerned by performance, you should use Vector over Array anywhere you can in the first place, and not always rely on default implementations, especially when they force the use of Array

结论是,如果你担心性能,你应该在任何地方使用Vector over Array,而不是总是依赖于默认实现,特别是当他们强制使用Array时

PS:same implementation with a for each() loop is 12x slower ...!

PS:每个()循环的相同实现速度慢12倍......!

#8

This depends on real world application requirements.

这取决于实际应用要求。

If your question is merely hypothetical, then the basics have already been explained. It is a typical search vs. sort problem. It has already been mentioned that algorithmically you are not going to achieve better than O(n) for that case.

如果你的问题只是假设,那么基本原理已经解释过了。这是典型的搜索与排序问题。已经提到过,在算法上你不会比O(n)更好地实现这种情况。

However, if you are looking at practical use, things get more interesting. You would then need to consider how large the array is, and the processes involved in adding and removing from the data set. In these cases, it can be best to take the computational 'hit' at insertion / removal time by sorting on the fly. Insertions into a pre-sorted array are not that expensive.

但是,如果您正在寻找实际用途,事情会变得更有趣。然后,您需要考虑数组的大小,以及添加和删除数据集所涉及的过程。在这些情况下,最好在插入/移除时通过动态排序来计算“命中”。插入预先排序的数组并不昂贵。

The quickest query response to the Min Max request will always be from a sorted array, because as others have mentioned, you simply take the first or last element - giving you an O(1) cost.

对Min Max请求的最快查询响应将始终来自已排序的数组,因为正如其他人所提到的,您只需要获取第一个或最后一个元素 - 给您一个O(1)成本。

For a bit more of a technical explanation on the computational costs involved, and Big O notation, check out the Wikipedia article here.

有关计算成本和Big O表示法的更多技术解释,请查看*文章。

Nick.

#9

If you are building the array once and want to find the maximum just once, iterating is the best you can do.

如果您要构建一次数组并且只想找到一次最大值,那么迭代是您可以做的最好的。

When you want to modify the array and occasionally want to know the maximum element, you should use a Priority Queue. One of the best data structures for that is a Fibonacci Heap, if this is too complicated use a Binary Heap which is slower but still good.

如果要修改数组并偶尔想知道最大元素,则应使用优先级队列。其中一个最好的数据结构是Fibonacci Heap,如果这太复杂,可以使用速度较慢但仍然很好的二进制堆。

To find minimum and maximum, just build two heaps and change the sign of the numbers in one of them.

要找到最小值和最大值,只需构建两个堆并更改其中一个数字的符号。

#10

Please take into account that sorting the array will only be faster that looping up to certain size of the array. If your array is small (and it will be like that any time) then your solution is perfectly fine. But if it might get too large you should use a conditional to use the sort approach when the array is small, and the normal iteration when it is too large

请注意,对数组进行排序只会更快地循环到特定大小的数组。如果您的阵列很小(并且它会随时都是这样)那么您的解决方案就完全没问题了。但是如果它可能变得太大你应该使用条件来在数组很小时使用排序方法,并在它太大时使用正常迭代

#11

If you want to find both the min and max at the same time, the loop can be modified as follows:

如果要同时找到最小值和最大值,可以按如下方式修改循环:

int min = int.maxValue;
int max = int.minValue;

foreach num in someArray {
  if(num < min)
    min = num;
  if(num > max)
    max = num;
}

This should get achieve O(n) timing.

这应该达到O(n)时间。

#12

Shortest way :

最短的方式:

Math.min.apply(null,array); //this will return min value from array
Math.max.apply(null,array); //this will return max value from array

Math.min.apply(NULL,数组); //这将从数组Math.max.apply(null,array)返回最小值; //这将从数组返回最大值

otherway of getting min & max value from array

另外从数组中获取最小值和最大值

 function maxVal(givenArray):Number
    {
    var max = givenArray[0];
    for (var ma:int = 0; ma<givenArray.length; ma++)
    {
    if (givenArray[ma] > max)
    {
    max = givenArray[ma];
    }
    }
    return max;
    }

    function minVal(givenArray):Number
    {
    var min = givenArray[0];
    for (var mi:int = 0; mi<givenArray.length; mi++)
    {
    if (givenArray[mi] < min)
    {
    min = givenArray[mi];
    }
    }
    return min;
    }

As you can see, the code in both of these functions is very similar. The function sets a variable - max (or min) and then runs through the array with a loop, checking each next element. If the next element is higher than the current, set it to max (or min). In the end, return the number.

如您所见,这两个函数中的代码非常相似。该函数设置一个变量 - max(或min),然后使用循环遍历数组,检查每个下一个元素。如果下一个元素高于当前值,则将其设置为max(或min)。最后,返回号码。

#13

There are a number of ways this can be done.

有很多方法可以做到这一点。

1. Brute force. Linear search for both min and max separately. (2N comparisons and 2N steps)

蛮力。分别线性搜索最小值和最大值。 (2N比较和2N步骤)

2. Iterate linearly and check each number for both min and max. (2N comparisons)

线性迭代并检查每个数字的最小值和最大值。 (2N比较)

3. Use Divide and conquer. (Between 2N and 3N/2 comparisons)

使用分而治之。 (2N和3N / 2比较之间)

4. Compare by pairs explained below (3N/2 Comparisons)

比较下面解释的对(3N / 2比较)

How to find max. and min. in array using minimum comparisons?

如何找到最大值和分钟。在数组中使用最小比较?

---

If you are really paranoid about speed, runtime & number of comparisons, also refer to http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

如果您对速度,运行时间和比较次数非常偏执,请参阅http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

#14

Algorithm MaxMin(first, last, max, min)

算法MaxMin(first,last,max,min)

//This algorithm stores the highest and lowest element

//此算法存储最高和最低元素

//Values of the global array A in the global variables max and min

//全局变量max和min中全局数组A的值

//tmax and tmin are temporary global variables

// tmax和tmin是临时全局变量

{
if (first==last) //Sub-array contains single element
 {
    max=A[first];
    min=A[first];
 }
 else if(first+1==last) //Sub-array contains two elements
  {
     if(A[first]<A[Last])
      {
      max=a[last];  //Second element is largest
      min=a[first]; //First element is smallest
      }
   else
   {
     max=a[first]; //First element is Largest 
     min=a[last];  //Second element is smallest
   }
}
else
 //sub-array contains more than two elements
{
 //Hence partition the sub-array into smaller sub-array 
 mid=(first+last)/2;
 //Recursively solve the sub-array
 MaxMin(first,mid,max,min);
 MaxMin(mid+1,last,tmax,tmin);
 if(max<tmax)
  {
     max=tmax;
  }
    if(min>tmin)
  {
   min=tmin;
  }
 }
}

#15

Below is Solution with o(n):-

以下是o(n)的解决方案: -

public static void findMaxAndMinValue(int A[]){
    int min =0, max = 0;
    if(A[0] > A[1] ){
        min = A[1];
        max = A[0];
    }else{
        max = A[1];
        min = A[0];
    }
    for(int i = 2;i<A.length ;i++){
        if(A[i] > max){
            max = A[i];
        }
        if(min > A[i]){
            min = A[i];
        }
    }
    System.out.println("Maxinum Value is  "+min+" & Minimum Value is  "+max);
}

#16

Amazed no-one mentioned parallelism here.

惊讶没有人提到这里的并行性。

If you got really a huge array, you can use parallel-for, on sub ranges. In the end compare all sub-ranges. But parallelism comes width some penalty too, so this would not optimize on small arrays. However if you got huge datasets it starts to make sense, and you get a time division reduction nearing the amount of threads performing the test.

如果你真的有一个巨大的数组,你可以在子范围上使用parallel-for。最后比较所有子范围。但并行性也会使宽度受到一些惩罚,所以这不会在小数组上进行优化。但是,如果您拥有庞大的数据集,它就会开始变得有意义,并且您可以将时间分割减少到接近执行测试的线程数量。

#17

Find max values from a array Let's see how to obtain min, max values by using a single funtion

从数组中查找最大值让我们看一下如何使用单个函数获取最小值,最大值

public void findMaxValue(){
   int[] my_array = {1,2,,6,5,8,3,9,0,23};
   int max = my_array[0];
   for(int i=1; i<my_array.length; i++)
   {
      if(my_array[i] > max)
         max = my_array[i];
   }
   return max; 
}

same thing can do for find min value

同样的事情可以找到最小值

#18

After reading everyone's comments (thank you for your interest), I found that the "best" way (least amount of code, best performing) to do this was to simply sort the Array, and then grab the first value in the Array:

在阅读了所有人的评论后(感谢您的兴趣),我发现执行此操作的“最佳”方式(代码量最少,性能最佳)只是对数组进行排序,然后获取数组中的第一个值:

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

myArray.sort(Array.NUMERIC);

var minValue:int = myArray[0];

This also works for an Array of Objects - you simply use the Array.sortOn() function and specify a property:

这也适用于对象数组 - 您只需使用Array.sortOn()函数并指定属性:

// Sample data
var myArray:Array /* of XML */ = 
    [
    <item level="2" name="a" />
    <item level="3" name="b" />
    <item level="3" name="c" />
    <item level="2" name="d" />
    <item level="5" name="e" />
    ]

// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);

var lowestLevel:int = myArray[0].@level;

I hope this helps someone else someday!

我希望有一天能帮助别人!