Warm tip: This article is reproduced from stackoverflow.com, please click
arrays java sorting

Can't spot a the problem in my code for array assortment in Java

发布于 2020-03-27 15:42:06

So i have an assignment, i need to turn all 1's in an array into the distance from the closest 0. And so when i run it, the last number in the output stays as 1, when it should have changed into a 2. can someone help me spot my mistake?

Basically what zeroDistance does, is pass the array once, changing all values, then runs from the back and changes them all again.

    public static void zeroDistance (int [] a)
{
    int counter = 0;
    for (int i = 0; i < a.length; i++)
    {
        if (a[i] == 0)
            counter = 0;
        if (a[i] == 1)
        {
            counter++;
            a[i] = counter;
        }
    }
    counter = 0;
    for (int i = a.length - 1; i >= 0; i--)
    {
        if (a[i] == 0)
            counter = 0;
        if (a[i] != 0)
        {
            counter++;
            if (a[i] > counter)
                a[i] = counter;
        }
    }
}

Input:

int[] a={0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1};

Output:

zeroDistance method result : 
0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 1
Should return : 
0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2
Questioner
Froggy
Viewed
37
Philippe B. 2020-01-31 18:59

Your problem comes from the second loop. Since you start over from the end of the array, your second loop considers that you have encountered a 0 at the end of your array, which is obviously not the case here.

So according to your code in your second loop if (a[i] > counter) will be true, since a[1] is 2 and counter is 1 in your first iteration, that leading to your last member of your array being 1 in your result.

As other people said. Don't change values before you encounter a zero. Don't assume that the end of your array is a 0. If you want to fix your problem you can set counter = a[a.length - 1]; before your second loop. But that is not very sexy, I think you can come up with another approach for your problem.

Hope this helps.

EDIT

As Robby pointed out. You will also get a problem in your first loop if you have a 1 at the beginning.

That being said, here is a version that seems to work on my side. Don't hesitate to point out any error.

public static void zeroDistance (int[] a)
{
    List<Integer> zerosCoordinates = new ArrayList<>();

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

        if (a[i] == 0)
            zerosCoordinates.add(i);
    }

    for(int i : zerosCoordinates) {

        for (int j = i - 1, k = 1; j >= 0; j--, k++) {

            if (a[j] == 0)
                break;

            if (a[j] != 0 && a[j] < k)
                a[j] = k;
        }
    }

    for (int i : zerosCoordinates) {

        for (int j = i + 1, k = 1; j < a.length; j++, k++) {

            if (a[j] == 0)
                break;

            if (a[j] != 0 && a[j] > k || j == a.length - 1)
                a[j] = k;
        }
    }

    for (int i = 0; i < a.length; i++)
        System.out.print(a[i]);
}

There is surely a better way to do this. I did it in a rush sorry about that.