Different values in array

Question

I'm using Java, I'm trying to get all the different values from 2d array with recursive function only and without use HashSet ArrayList etc.., The values will be only [0-9] i.e:

{{4,2,2,1,4},{4,4,3,1,4},{1,1,4,2,1},{1,4,0,2,2},{4,1,4,1,1}}; -> Returns 5 (Because 4,2,3,1,0)
{{4,6,2,1,4},{4,4,3,1,4},{1,1,4,2,1},{1,4,0,2,2},{4,1,4,1,1}}; -> Returns 6 (Because 4,2,3,1,0,6)
{{4,4,4,4,4}}; -> Returns 1 (4)

What I tried:

public static int numOfColors(int[][] map) {
    int colors = 0;
    if (map == null || map.length == 0) {
        return colors;
    } else {
        int[] subArr = map[map.length - 1];

        for (int i = 0; i < subArr.length; i++) {
            int j = i + 1;
            for (; j < subArr.length; j++) {
                if (subArr[i] == subArr[j]) {
                    break;
                }
            }
            if (j == subArr.length) {
                int k = 0;
                for (; k < map.length - 1; k++) {
                    for (int l = 0; l < map[k].length; l++) {
                        if (subArr[i] == map[k][l]) {
                            continue;
                        }
                    }
                }
                if (k == map.length - 1) {
                    colors++;
                }
            }
        }
        int[][] dest = new int[map.length - 1][];
        System.arraycopy(map, 0, dest, 0, map.length - 1);
        colors += numOfColors(dest);

        return colors;
    }
}

But this hasn't worked for me, where is the miskate?

You need some kind of storage to know if you have seen the values before, or delete all instants of a value after you count them, so sum up the colors for each sub-arrays won't work. Also, recursion seems a strange choice here since it doesn't simplify the problem nor make the solution more efficient — Cash Lo
– Cash Lo, Commented Jan 3, 2017 at 9:08
Questions seeking debugging help ("why isn't this code working?") must include the desired behavior, a specific problem or error and the shortest code necessary to reproduce it in the question itself. Questions without a clear problem statement are not useful to other readers. See: How to create a minimal reproducible example — Erwin Bolwidt
– Erwin Bolwidt, Commented Jan 3, 2017 at 9:08

Adamo · Accepted Answer · 2017-01-03 10:20:15Z

2

Recursion doesn't make much sense here. Just use a simple array as storage, and count the instances of different values, if you know the range (0-9) then a simple int[] will be sufficient.

This should do the trick:

public static int numOfColors(int[][] map){

    int[] storage = new int[10];

    //iterate through all the values
    for(int i = 0; i<map.length; i++){
        for(int j = 0; j<map[0].length; j++){

            //will throw an Exception if an entry in map is not 0-9
            //you might want to check for that
            storage[map[i][j]]++;

        }
    }

    int colors = 0;
    //now check which values exist.
    for(int i = 0; i<storage.length; i++){
        if(storage[i] != 0) colors++;
    }

    return colors;
}

edited Jan 3, 2017 at 10:20

answered Jan 3, 2017 at 9:46

Adamo

211 silver badge5 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Vlad Bochenin · Accepted Answer · 2017-01-03 09:25:25Z

As it was already mentioned by @Cash Lo, you need some kind of storage. So you algorithm could looks something like:

@Test
public void numOfColorsTest() {
    int[][] map = new int[][] {{4,2,2,1,4},{4,4,3,1,4},{1,1,4,2,1},{1,4,0,2,2},{4,1,4,1,1}};
    System.out.println(String.format("numOfColors: %s", numOfColors(map, new int[0], map.length-1)));

    map = new int[][] {{4,6,2,1,4},{4,4,3,1,4},{1,1,4,2,1},{1,4,0,2,2},{4,1,4,1,1}};
    System.out.println(String.format("numOfColors: %s", numOfColors(map, new int[0], map.length-1)));

    map = new int[][] {{4,4,4,4,4}};
    System.out.println(String.format("numOfColors: %s", numOfColors(map, new int[0], map.length-1)));
}

public static int numOfColors(int[][] map, int[] collector, int currentPosition) {
    int[] result = collector;
    if (currentPosition < 0) {
        return collector.length;
    }
    for (int color : map[currentPosition]) {
        boolean found = false;
        for (int aResult : result) {
            if (aResult == color) {
                found = true;
                break;
            }
        }
        if (!found) {
            int[] newResult = new int[result.length + 1];
            System.arraycopy(result, 0, newResult, 0, result.length);
            newResult[newResult.length - 1] = color;
            result = newResult;
        }
    }
    return numOfColors(map, result, currentPosition-1);
}

g-t · Accepted Answer · 2017-01-03 09:20:32Z

I know that this is not the answer but you should always think if your solution makes sense.

In my opinion using recursion here is very bad idea because:

the code isn't readable at all
I haven't checked that but I doubt it's more efficient
recursion is hard to debug
you're making really simple problem complicated

Consider the following code. It does exactly what you need:

Integer[][] array = {{4,2,2,1,4},{4,4,3,1,4},{1,1,4,2,1},{1,4,0,2,2},{4,1,4,1,1}};
int size = Arrays.stream(array)
        .flatMap(Arrays::stream)
        .collect(Collectors.toSet())
        .size();
System.out.println("size = " + size);

If you purposely use recursion in this case the only thing I can recommend is Test Driven Development. Write the algorithm and tests simultaneously.

Collectives™ on Stack Overflow

Different values in array

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related