increment numbers in an array until they are all e

问题:

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 7 years ago.

The goal of this program is to make all numbers in an array the same. You have to increment all values in the array except for one each time. Then the program will print out the minimum number of steps it would take to make all the numbers the same. I have what I believe is a working solution I just want to make it more efficient, does any one have any ideas? In the following code the user enters the initial values for the numbers into the array and then calculates the amount of steps required

public static void main(String[] args) throws NumberFormatException, IOException 
{
counter=0;
         size=sc.nextInt();
         input= new int[size];
        for(int k=0; k<size; k++)
        {
            input[k]=sc.nextInt();
        }
        while(!isAllEqual(input))
        {
            Arrays.sort(input);
            for(int k=0; k<input.length-1; k++)
            {
                input[k]++;
            }
            counter++;
        }
        pw.println(counter);

public static boolean isAllEqual(int[] a){
    for(int i=1; i<a.length; i++){
        if(a[0] != a[i]){
            return false;
        }
    }
return true;
}

回答1:

It might be easier to wrap your head around this if you change the step into something simpler. If we're only talking about equality between the values (i.e. relative, not absolute values), incrementing and decrementing all of the values at once makes no difference. If we change our step to "increment all but one, then decrement every value by one", we can see that incrementing all but one is equivalent to decrementing a single value.

Can you figure out the number of steps to make the values equal if the step is "decrement one value"? It should involve looping through the array two times at max, and no sorting.

回答2:

MAJOR EDIT AS I MISREAD THE QUESTION

Scan through the list just once to find the minimum value in the list and the total of adding all the values together.

Once you have these two values, the number of required increments is:

[total of all the values] - [number of items in list] * [minimum value]

In code:

public static int numberOfSteps(int[] a) {
    if( a.length==0 ) return 0;

    int min= a[0];
    int total = a[0];
    for(int i=1;i<a.length;i++) {
        if( a[i] < min ) min = a[i];
        total += a[i];
    }

    return total - a.length * min;
}

This works because (as Matti Virkkunen pointed out) the number of decrements for each item is (a[i] - min ) so for the entire list it is sum(a[i]-min) which we can expand to sum(a[i]-(length*min).

The corresponding increments would be at each step to increment everything except the right most item which is equal to the maximum. For example:

Initial state = (0,1,1,1) 1. increment everything except a[3] --> (1,2,2,1) 2. increment everything except a[2] --> (2,3,2,2) 3. increment everything except a[1] --> (3,3,3,3) : solution in three steps = (1+1+1) - (4 * 0)

and again, initial state of (1,2,3,3)

1. increment everything except a[3] --> (2,3,4,3)
2. increment everything except a[2] --> (3,4,4,4)
3. increment everything except a[3] --> (4,5,5,4)
4. increment everything except a[2] --> (5,6,5,5)
5. increment everything except a[1] --> (6,6,6,6) : solution in five steps = (1+2+3+3) - (4 * 1)