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

问题描述

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

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

I want to find the distance between the smallest and largest number in that array in O(n^2) time. It needs to be O(n^2) time as per the requirements of the assignment. To do this, I am writing a method called quadratic. So far I have come up with the code below.

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。

The problem is, when I run that method with array mentioned above, I get a max difference of 0. I expect 9, since the largest number is 10, and the smallest is 1. 10 - 1 = 9.

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

My question is, can someone show me how I can change my code so that it properly computes the max distance between the smallest and largest numbers?

推荐答案

重新覆盖最大值和最小值。

You're overwriting the max and mins.

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

您需要将当前数字与已设置的最大值/最小值进行比较。相反，您将当前数字与另一个数字进行比较，然后在条件为真时覆盖max / min。在此示例中，最大值是10，但是后来您检查了 if（9> 2），这是正确的，因此您更改了 max = 10 到 max = 9 。

You need to compare the current number with the max/min that is set already. Instead you're comparing the current number with another number, and then overwriting max/min if the condition is true. In this example, at one point 10 was the max, but then you later checked if(9>2), which is true, so you changed max = 10 to max = 9.

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

Here it is in O(n^2) time, with the outer loop being completely useless.

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

这篇关于如何编写O（n ^ 2）方法来查找两点之间的最大距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！