CODEWITHSUNDEEP
javaarraysalgorithm
Daniele
Daniele

Reputation: 4343

Algorithm to verify if a two-dimensional array has two equals rows

Define a method in which, given a two-dimensional array, evaluates if it has at least two identical rows

I've tried to come up with an algorithm to do it but I didn't go very far. This is what I got:

public static boolean righeUguali(int[][] a){
    boolean rUguali=false;

    for(int i=0; i<a.length; i++)
        for(int j=0; i<a[i].length; j++)
            if(Arrays.equals(a[i],a[j]))
                rUguali = true;
    return rUguali;

could you help me fix this code?

Upvotes: 3

Views: 459

Answers (4)

castletheperson
castletheperson

Reputation: 33516

By applying the simplest answer from the near-duplicate question:

public static boolean righeUguali(int[][] a) {
    for(int i = 0; i < a.length; i++)
        for(int j = i + 1; j < a.length; j++)
            if(Arrays.equals(a[i], a[j]))
                return true;
    return false;
}

Your algorithm is breaking because j is seemingly there to iterate over the nested array. That isn't needed because Arrays.equals will iterate over the nested array. Instead, use it as the second iterator for finding if any of the other elements match the current element specified by i.

If you want better performance, there are faster solutions on the duplicate question.

Upvotes: 2

j_random_hacker
j_random_hacker

Reputation: 51316

No one has yet mentioned that a much faster way is to sort the top-level array, and then look for two adjacent rows that are identical. If the array is m*n, this will take O(mn log n) time, as opposed to all existing solutions which take O(mn^2) time.

Of course, if you can't reorder the rows then you'll need to make a copy of the array first -- but unless your array takes up > 50% of available RAM, creating the copy and then sorting its rows will still be much faster than the existing solutions.

Upvotes: 1

fill͡pant͡
fill͡pant͡

Reputation: 1165

Here is how i would do it:

int[][] array = { { 1, 2, 3, 4, 5, 6 },
            { 7, 6, 8, 3 }, 
            { 1, 2, 3, 4 },
            { 1, 2, 3, 9, 5, 6, 32, 3125423 },
            { 8, 3 }, 
            { 1, 2, 3, 4, 5, 6 } };//same as first row
    external: for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (Arrays.equals(array[i], array[j])) {
                System.out.println("Row: " + i + " is the same as row: " + j+" (warning! 0 oriented!)" );
                break external;
            }
        }
    }

As you see, array[] is quite random, but the first row (row 0) is the same as the last (row 5) so what i do then, is to loop through the array once and in every pass loop through the remaining rows of the array. Then i compare the arrays to chech if they are the same. As you see the code prints out a message and then terminates (stoping the external loop)

This is based on a simple sort algorythm.

EDIT #1 As @4castle pointed out in the comments, in the context of a method the break statement is not required and can be replaced by return.

Upvotes: 2

MrSmith42
MrSmith42

Reputation: 10161

  • You need to ensure that you are not comparing the row with itself. You ensure that by starting j with i+1
  • Both loops need to iterate over the rows
  • The fist of the two rows cannot be the last one, otherwise there would be no second row left to compare it to.
  • optimization: you can terminate as soon as you found two equal rows

Here the modified code:

public static boolean righeUguali(int[][] a){
    for(int i=0; i<a.length-1; i++)
        for(int j=i+1; i<a.length; j++)
            if(Arrays.equals(a[i],a[j]))
                return true;
    return false;
}

Upvotes: 4

Related Questions