这是最有效的方法吗？

Question

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

您不需要对整个数组进行排序。您只能迭代一次并找到最小和最大的数字。我认为一个简单的 for 会更快。由于您对数组进行了一次迭代，因此复杂度将为 N。

            double smallest = ar[0];
            double largetst = ar[0];

            for(int i=1; i< ar.length; i++)
            {
                    if(ar[i] > largetst)
                            largetst = ar[i];
                    else if (ar[i] < smallest)
                            smallest = ar[i];

            }

           result = largest-smallest;

Answer 2

不先对数组进行排序，而是遍历它，收集最小值和最大值怎么样？

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

这是最有效的方法吗？

is this the most efficient way?

java

arrays

big-o