Finding duplicate values ​​between two arrays

Question

Let's say I have the following two arrays:

int[] a = [1,2,3,4,5]; int[] b = [8,1,3,9,4]; 

I would like to take the first value of array a - 1 - and see if it is contained in array b . So, I would understand that the “1” from a is in b , even if it is not in the same position. When I compare the first element in a , I will go to the next number in array a and continue the process until I completely go through the first array.

I know that I need to make a loop (perhaps nested?), But I can’t understand how I stick to only the first number in array a , sorting through all the numbers in array b .

It seems pretty simple, I just can't hug it around ...

Answer 1

All these decisions take O (n ^ 2) time. You should use hashmap / hashset for a much faster O (n) solution:

 void findDupes(int[] a, int[] b) { HashSet<Integer> map = new HashSet<Integer>(); for (int i : a) map.add(i); for (int i : b) { if (map.contains(i)) // found duplicate! } } 

Answer 2

Yes, you need two loops and yes, nested.

the pseudocode will look like this:

 for each in A do for each in B do if (current item of A equals to current item of B) say yes! done done 

Now you need to translate it into Java . Since this sounds like homework or some kind of exercise, you have to do it yourself.

Also, think about what kind of result you need. If you just need true / false, if a and b some common values, you can exit the loops as soon as you find the first match. If instead you need to count the number of common elements between arrays, you will need to reset the counter to this set of nested loops. I will leave it to you to find out this part.

Answer 3

You just need two nested loops for the loop

 for(int i = 0; i < a.length; i++) { for(int j = 0; j < b.length; j++) { if(a[i] == b[j]) { //value is in both arrays } } } 

What this means is to go to the first value of a and compare with each value in b, then go to the next value of a and repeat.

Answer 4

Since you do not have this marked as homework, I will give you the benefit of doubt. As you said, you will need two loops; loop foreach int in a[] and foreach int in b[] . Then just compare the two values ​​at each iteration, which gives you simple code:

 for (int x : a) { for (int y : b) { if (x == y) { System.out.println("a[] and b[] both contain " + x); } } } 

Answer 5

Depending on the data (its size, regardless of whether each value is unique, etc.) and what you are trying to extract from it (i.e. each element a is in b, as well as its index in b), it It may be helpful to do a bit of overhead before you make meat. For example, if you sort both arrays (which you only need to do once), you can start the inner loop where you stopped it last (since you know that you are looking for the number> = the one you were looking for last, so it should be by this index or more), and you can also stop the inner loop earlier (since you know that if you are looking for X and you did not find it before you see the value> X, then X is not). Another approach would be to load both values ​​into a set that you can now effectively probe.