如何编写一个找到两点之间最大距离的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];  
}

您需要将当前数字与已设置的最大/最小值进行比较.相反,您将当前数字与另一个数字进行比较,然后在条件为真时覆盖最大值/最小值.在这个例子中,在一个点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; 
}