如何编写O（n ^ 2）方法来查找两点之间的最大距离

Question

我有一个数组 int [] nums = {5, 1, 6, 10, 4, 7, 3, 9, 2}

我想在O（n ^ 2）时间中找到该数组中最小和最大数字之间的距离。根据分配要求，它需要O（n ^
2）时间。为此，我正在编写一种名为的方法quadratic。到目前为止，我已经提出了以下代码。

public static int quadratic(int[] nums) {

    int max = nums[0];
    int min = nums[0];

    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length; j++) {

            if (nums[i] > nums[j])
                max = nums[i];
            else if (nums[i] < nums[j])
                min = nums[i];  
            }
        }

    int maxDifference = max - min;
    return maxDifference; 
}

问题是，当我使用上述数组运行该方法时，我得到的最大差为0。我期望9，因为最大的数字是10，最小的数字是1。10-1 = 9。

我的问题是，有人可以告诉我如何更改代码，以便正确计算最小和最大数字之间的最大距离吗？

Answer 1

您正在覆盖最大和最小。

if (nums[i] > nums[j])
    max = nums[i];
else if (nums[i] < nums[j])
    min = nums[i];  
}

您需要将当前数字与已设置的最大值/最小值进行比较。相反，您将当前数字与另一个数字进行比较，如果条件为true，则覆盖max /
min。在此示例中，最大值是10，但是后来您检查了if(9>2)，这是对的，因此您将其更改max = 10为max = 9。

这里是O（n ^ 2）时间，外循环完全没用。

public static int quadratic(int[] nums) {

    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;

    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length; j++) {

            if (nums[j] > max)
                max = nums[j];
            if (nums[j] < min)
                min = nums[j];  
            }
        }
    System.out.println(max + " " + min);
    int maxDifference = max - min;
    return maxDifference; 
}