这是最有效的方式吗？

Question

我正在寻找列表中2个双打之间最大的区别,我在NlogN时间这样做了,有没有办法在线性时间内完成它？谢谢!

public static double NlogN(double[] ar){
    Arrays.sort(ar);
    double max=ar[ar.length-1];
    double min=ar[0];
    double difference=max-min;
    return difference;
}

Answer 1

如何不首先排序数组,而只是遍历它,收集最小值和最大值？

public static double linear(double[] ar) {
    double max = Double.NEGATIVE_INFINITY;
    double min = Double.POSITIVE_INFINITY;

    for(double elem: ar){
        if(min > elem) {min = elem;}
        if(max < elem) {max = elem;}
    }

    return Math.abs(max-min); 
}