java - 这是最有效的方法吗？

Question

我正在寻找列表中两个 double 之间的最大差异，我已经在 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); 
}