How to write a O(n^2) method that finds the larges

问题:

I have an array int [] nums = {5, 1, 6, 10, 4, 7, 3, 9, 2}

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

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?

回答1:

You're overwriting the max and mins.

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

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.

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

回答2:

For numbers (as opposed to points on a plane) You can do that in linear time. Find maximum, find minimum, then subtract. So, no nested loops required.