从数组中获得最小值或最大值的最佳方法是什么？
假设我有一组数字： [2,3,3,4,2,2,5,6,7,2]
在数组中find最小值或最大值的最佳方法是什么？
现在，为了获得最大值，我循环访问数组，如果variables大于现有值，则将其重置为该值：
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()可以使用任意数量的参数。 此外，了解可用于Function对象的apply()方法也很重要。 它允许您使用Array将parameter passing给函数。 让我们利用两者：
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循环search最小值或最大值要快。
没有任何可靠的方法来获取最小/最大值，而不需要testing每个值。 你不想尝试sorting或类似的东西，遍历数组是O（n），比任何sortingalgorithm在一般情况下都要好。
如果
- 该数组没有sorting
- 查找最小值和最大值是同时完成的
然后有一个algorithm可以find3n / 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给出的recursion解决scheme可能也实现了这种最小数量的比较（最后一行需要改变）。 但是在相同数量的比较中，迭代解决scheme总会因为函数调用的开销而击败recursion解决scheme，正如他所提到的那样。 但是，如果只关心寻找几个数字的最小和最大值（就像Eric Belair所做的那样），那么没有人会注意到今天的计算机与上述任何方法的区别。 对于大型arrays，差异可能是显着的。
尽pipe这个解决scheme和Matthew Brubaker给出的解决scheme具有O（n）的复杂性，但实际上应该仔细评估所涉及的隐藏常量。 他的解决scheme的比较数是2n。 使用3n / 2比较解决scheme获得的加速比2n比较明显。
除非数组被sorting，否则这是最好的。 如果它被sorting，只需要第一个和最后一个元素。
当然，如果没有sorting，那么首先sorting并抓取第一个和最后一个是保证效率比循环一次。 即使是最好的sortingalgorithm也必须不止一次地查看每个元素（每个元素的平均O（logN）次），总计为O（N * LogN）。
如果您想要快速访问数据结构中的最大元素，请查看堆以便以某种顺序保持对象的有效方法。
你必须遍历数组，没有其他方式来检查所有的元素。 只需对代码进行一次修正 – 如果所有元素均为负数，则最后的maxValue将为0。 您应该使用整数的最小可能值对其进行初始化。
如果要多次search数组，最好首先对数组进行sorting，而不是search更快（二进制search），最小和最大元素只是第一个和最后一个。
取决于你所说的“最好”。 从理论的angular度来看，在一个确定性的图灵机器中，你不能解决问题小于O(n) 。
天真的algorithm太循环，并更新最小，最大。 但是，如果您想同时获取min，max，则recursion解决scheme所需的比较比朴素algorithm的比较要less（由于函数调用开销不一定更快）。
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) } ; }
最简单的解决办法是sorting并得到第一个和最后一个项目，但显然不是最快的;）
find最小值或最大值的最佳解决scheme（性能方面）是您编写的单纯循环algorithm。
Math.max（）实际上是as3代码编译到AVM2操作码，因此不是比任何其他as3代码更“原生”。 因此，这不一定是最快的实施。
实际上，鉴于它在数组types上工作，它比仔细编写的代码usignvector：
我使用gskinner的PerformanceTest（向量和数组填充了相同的随机数字），对Math.max的几个简单的Vector和Array实现进行了快速基准比较。 使用AIR SDK / release player（使用AIR SDK 14编译的Flash Player WIN 14,0,0,122 RELEASE），最快的Vector实现看起来比Math.max快3倍以上：
对于1,000,000个数值，平均值为3.5毫秒，而Math.max（）的平均值为11毫秒：
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; }
结论是，如果你担心性能，你应该首先使用Vector over Array，而不是总是依赖默认的实现，特别是当他们强制使用Array
PS：与每个（）循环相同的实现是慢12倍…！
这取决于现实世界的应用需求。
如果你的问题只是假设的话，那么基础已经被解释了。 这是一个典型的search与sorting问题。 已经提到，在algorithm上你不会比O（n）更好。
但是，如果您正在实际使用，事情会变得更有趣。 然后，您需要考虑数组的大小以及从数据集中添加和删除的过程。 在这些情况下，最好是在插入/移除时通过在飞行中进行sorting来计算“命中”。 插入到预先sorting的数组中并不昂贵。
Min Max请求最快的查询响应将始终来自已sorting的数组，因为正如其他人所提到的，您只需取第一个或最后一个元素 – 给您一个O（1）成本。
有关所涉及的计算成本和Big O符号的更多技术解释，请查看Wikipedia文章。
缺口。
如果你正在构build一个数组并且想要只find一次最大值，迭代就是你能做的最好的。
当你想修改数组，偶尔想知道最大元素时，应该使用优先级队列 。 其中最好的数据结构之一就是斐波那契堆 ，如果这太复杂的话，可以使用一个比较慢但仍然好的二进制堆 。
为了find最小和最大，只需build立两堆，并在其中之一改变数字的符号。
请考虑sorting数组只会更快，循环到一定的数组大小。 如果你的数组很小（并且随时都会这样），那么你的解决scheme是完全正确的。 但是，如果它可能太大，你应该使用条件来使用sorting的方法，当数组很小，正常迭代时，它是太大
如果您想同时查找最小值和最大值，则循环可以修改如下：
int min = int.maxValue; int max = int.minValue; foreach num in someArray { if(num < min) min = num; if(num > max) max = num; }
这应该达到O（n）的时间。
最短path：
Math.min.apply（NULL，数组）; //这将返回数组的最小值
Math.max.apply（NULL，数组）; //这将从数组中返回最大值
从数组中获取最小值和最大值的另一种方式
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; }
正如你所看到的，这两个函数中的代码非常相似。 该函数设置一个variables – 最大（或最小），然后通过循环遍历数组，检查每个下一个元素。 如果下一个元素高于当前值，则将其设置为最大值（或最小值）。 最后，返回号码。
有很多方法可以做到。
- 蛮力。 线性search最小值和最大值分别。 （2N比较和2N步骤）
- 线性迭代并检查每个数字的最小值和最大值。 （2N比较）
- 使用分而治之。 （在2N和3N / 2之间比较）
- 下面解释对比（3N / 2比较）
如何查找最大值 和分钟。 在数组中使用最小的比较？
如果你对速度，运行时间以及比较次数有偏执的话，请参考http://www.geeksforgeeks.org/maximum-and-minimum-in-array/
algorithmMaxMin（第一，最后，最大，最小）
//这个algorithm存储最高和最低的元素
//全局variablesmax和min中全局数组A的值
// tmax和tmin是临时的全局variables
{ 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; } } }
以下是o（n）的解决scheme： –
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); }
在阅读了所有人的评论（感谢您的关注）之后，我发现“最好”的方式（代码最less，performance最好）是简单地对Array进行sorting，然后获取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];
这也适用于一个对象数组 – 您只需使用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;
我希望这有助于别人有一天！
