How to compare two arrays of integers without regard to order

Question

I want Java code to be able to compare this way (for example):

<1 2 3 4> = <3 1 2 4> <1 2 3 4> != <3 4 1 1> 

I cannot use a hashmap table or anything else; just clean code without a library.

I know that there are two ways.

• sort them and compare array index by index

• use two for loops and compare the outer index with the inner index. I tried with this, but still did not work:

   for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(a[i] != a[j] && j == n) return false; } } return true; 

Is there something wrong with the code? thanks

Answer 1

Sort and compare. You cannot get complexity better than this, and any “improvement” you make at speed risks that your code will be wrong.

[edit] Actually .... if you know that your numbers are relatively small (for example, say: arrays contain only digits from 0 to 1000), then there is an alternative in O (n). Something like this (sorry if the syntax is wrong, I haven't used java lately):

 int count[1001]; // already intialized to 0 for(int i=0;i<n;i++){ count[a[i]]++; count[b[i]]--;} bool arrays_identical = true; for(int i=0;i<=1000 && arrays_identical; i++) arrays_identical &= count[i]==0; 

Disclaimer: this code does not contain “sanity checks” (that is, arrays do have a length of “n”, numbers are given in a given interval) - this is only to illustrate the principle.

Answer 2

 Arrays.sort(a); Arrays.sort(b); return Arrays.equals(a, b); 

Answer 3

Since this is homework, I'm going to guess that a simple quadratic solution (which is your initial attempt) is fine. In this case, you can do something like this:

 int count(int[] nums, int x) { int count = 0; for (int num : nums) { if (num == x) count++; } return count; } boolean equals(int[] arr1, int[] arr2) { if (arr1.length != arr2.length) return false; for (int x : arr1) { if (count(arr1, x) != count(arr2, x)) return false; } return true; } 

It sacrifices speed for clarity: obviously right!

Advice

• Use for everyone when applicable; It is always readable for better readability.
• Assistant features improve readability and reuse!

Answer 4

I think it would be wise to verify that the lengths of both arrays are equal before performing any iteration. This is a cheap way to give up hard work at an early stage, and it captures the following type of failure for the second approach you mention:

{1, 2, 3} is considered equal to {4, 3, 2, 1}

Answer 5

This is an O (n ^ 2) problem. No other solution is faster than comparing two arrays directly.

Virgil's solution is cool, except that it is not O (n) performance. This is really O (n + 1000). A second array comparison for setting a boolean is expensive and the reverse is failing in small arrays.

The solution you wrote is the best, with the exception of errors.

Here is the bug fixed.

 boolean[] matchedPositions = new boolean[n]; for(int k = 0; k < n; k++ { matchedPositions[k] = false; } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(matchedPositions[j] == false && a[i] == a[j]) { matchedPositions[j] = true; break; } if(j == n - 1) { return false; } } } return true; 

In this case, if in the case when the integer matches, then the inner loop will be broken and set or mark the matching position. This is necessary for arrays with duplicate entries , this will avoid two entries in the left array corresponding to one entry in the correct array.

If, in the event that a match does not occur that is identified by j == n - 1 , you will return false.

Since we expect false by default in boolean, it is better to specify the initialize flag.

In fact, this solution has an O (n log n + n) performance penalty. Sorting and comparison have O (n ^ 2 + n) performance limitation. Sorting has an O (n ^ 2) performance and one loop for checking. But sorting modifies the contents of the array, and it is not.

Answer 6

Here is the fix for the code you posted.

 for(int i = 0; i < n; i++) { int j; for(j = 0; j < n; j++) { if(a[i] == b[j]) break; } if (j == n) return false; } return true; 

However, this algorithm will be split into arrays containing duplicates. For example, the array {1, 1, 2, 3} will be found as a match with the array {1, 2, 2, 3} .

I highly recommend that you do a sort and compare algorithm instead.

Answer 7

if you take one array as 1,2,3,4,3,1,2,4 then the solution will be that way.

2n = total number of integers: 8

 //program int i, j, n = 4; for(i = 0; i < n; i++) for(j = n; j < 2n; j++) { if( a[i] != a[j]) { j++; } else { i++; exit(); } } if (i == n) { //They both are equal; } else if(i != n) { //They both are not equal; } 

If it does not work, comment on it. Thanks.

Answer 8

Before you start a more complex computational solution, you can run a quick O (n) test to see if the arrays are the same. There are times when this will lead to a false positive, and you can use more intensive computing tools for further study. If it returns false, you can be sure that the arrays are different.

The main approach is to make a cumulative XOR between the i elements of two arrays. If the resulting XOR is nonzero, you know that two arrays are different from each other. If XOR is zero, they may be the same, but more work is required to confirm.

 int c_xor = 0; // XOR accumulator for (int i = 0; i < n; ++i) c_xor ^= arr1[i] ^ arr2[i]; // They're different if c_xor != 0; the might be the same if c_xor == 0 return c_xor == 0;