确定数字数组中高低的最佳算法？

Question

我在这里使用伪代码,但这是在JavaScript中.使用最有效的算法,我试图找到高和低给定一组正整数.这就是我想出来的,但我不认为这可能是最好的,只是想知道是否有人有任何其他建议.

var low = 1;
var high = 1;
for ( loop numbers ) {
    if ( number > high ) {
        high = number;
    }
    if ( low == 1 ) {
        low = high;
    }
    if ( number < low ) {
        low = number;
    }
}

Answer 1

将high和low初始化为第一个元素.比挑选任意"高"或"低"数字更有意义.

var myArray = [...],
    low = myArray[0],
    high = myArray[0]
;
// start looping at index 1
for (var i = 1, l = myArray.length; i < l; ++i) {
    if (myArray[i] > high) {
        high = myArray[i];
    } else if (myArray[i] < low) {
        low = myArray[i];
    }
}

或者,避免需要多次查找数组:

for (var i = 1, val; (val = myArray[i]) !== undefined; ++i) {
    if (val > high) {
        high = val;
    } else if (val < low) {
        low = val;
    }
}

Answer 2

你必须及时完成它,O(n)因为你需要循环遍历所有n元素()以检查它们,因为任何一个元素可能是最小值或最大值.(除非它们已经排序.)

换句话说,你需要遍历所有元素并像你一样进行最大和最小的检查.

排序通常充其量O(n*log(n)).因此它比单次扫描(O(n))更慢.

Answer 3

您的示例几乎是最有效的算法,但显然当所有数字小于1或大于1时它将不起作用.此代码适用于以下情况:

var low = numbers[0]; // first number in array
var high = numbers[0]; // first number in array
for ( loop numbers ) {
    if ( number > high ) {
        high = number;
    }
    if ( number < low ) {
        low = number;
    }
}

Answer 4

如果列表很小("小"小于几千个元素)并且你没有做太多("多"少于几千次),那就没关系了. 在您担心优化最大/最小算法之前,首先分析您的代码以找到真正的瓶颈.

现在回答你提出的问题.

因为没有办法避免查看列表中的每个元素,所以线性搜索是最有效的算法.它需要N次,其中N是列表中元素的数量.在一个循环中完成所有操作比调用max()然后调用min()(需要2*N时间)更有效.所以你的代码基本上是正确的,尽管它没有考虑负数.这是在Perl.

# Initialize max & min
my $max = $list[0];
my $min = $list[0];
for my $num (@list) {
     $max = $num if $num > $max;
     $min = $num if $num < $min;
}

排序然后抓取第一个和最后一个元素效率最低.它需要N*log(N),其中N是列表中元素的数量.

最有效的最小/最大算法是每次添加元素或从列表中删除时重新计算最小值/最大值的算法.实际上,每次都缓存结果并避免线性搜索.然后花在此上的时间是列表更改的次数.它最多需要M次,其中M是变化的数量,无论你调用多少次.

为此,您可以考虑使搜索树保持其元素的顺序.根据您使用的树样式,获取该结构中的最小值/最大值为O(1)或O(log [n]).