Missing elements from two arrays in java

Question

How can we detect missing elements from two arrays? Example:

int []array1 ={1,2,3,4,5}; int []array2 ={3,1,2}; 

From the two arrays above, I want to find which missing elements in the second array?

Answer 1

Convert them to Set and use removeAll .

The first problem is how to convert the int[] primitive to a collection. With Guava, you can use:

 List<Integer> list1 = Ints.asList(array1); List<Integer> list2 = Ints.asList(array2); 

The Apache community (which I am not familiar with) seems to have something similar.

Now convert to set:

 Set<Integer> set1 = new HashSet<Integer>(list1); 

And calculate the difference:

 set1.removeAll(list2); 

And convert the result to an array:

 return Ints.toArray(set1); 

Answer 2

If you are allowed to duplicate in arrays, an effective (O (n)) solution is to create a frequency table (Map) by iterating over the first array, and then use the map to match any elements in the second array.

 Map<Integer, Integer> freqMap = new HashMap<Integer, Integer>(); // Iterate over array1 and populate frequency map whereby // the key is the integer and the value is the number of // occurences. for (int val1 : array1) { Integer freq = freqMap.get(val1); if (freq == null) { freqMap.put(val1, 1); } else { freqMap.put(val1, freq + 1); } } // Now read the second array, reducing the frequency for any value // encountered that is also in array1. for (int val2 : array2) { Integer freq = freqMap.get(val2); if (freq == null) { freqMap.remove(val2); } else { if (freq == 0) { freqMap.remove(val2); } else { freqMap.put(freq - 1); } } } // Finally, iterate over map and build results. List<Integer> result = new LinkedList<Integer>(); for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) { int remaining = entry.getValue(); for (int i=0; i<remaining; ++i) { result.add(entry.getKey()); } } // TODO: Convert to int[] using the util. method of your choosing. 

Answer 3

You can use Set and its methods. This operation will be a definite difference.

Answer 4

A naive way would be to simply look for one array for each of the elements of another array (with a for loop). If you first used SORT for both arrays, it has become much more efficient.

Answer 5

Consider the intersection method:

A healthy discussion is available at:

http://www.coderanch.com/t/35439/Programming-Diversions/Intersection-two-arrays

Answer 6

@finnw I think you were thinking of collections of collections . You must import org.apache.commons.collections.CollectionUtils; To get the disjunction function.

Using the disjunction method will find all objects that are not found at the intersection.

 Integer[] array1 ={1,2,3,4,5}; Integer[] array2 ={3,1,2}; List list1 = Arrays.asList(array1); List list2 = Arrays.asList(array2); Collection result = CollectionUtils.disjunction(list1, list2); System.out.println(result); // displays [4, 5] 

Answer 7

You can create two other int arrays to store the multiplicity of each value. Increase the index of the array that matches the value each time it is found, and then compare the arrays.

This is not the most “efficient” way, but it is a very simple concept that works.

Answer 8

Guava library may be useful; you need to change the Array to Set and then use the API.

Answer 9

This is not the most efficient way, but it may be the easiest way to work in Java:

 public static void main(final String[] args) { final int[] a = { 1, 2, 3, 4, 5 }; final int[] b = { 3, 1, 2 }; // we have to do this just in case if there might some values that are missing in a and b // example: a = { 1, 2, 3, 4, 5 }; b={ 2, 3, 1, 0, 5 }; missing value=4 and 0 findMissingValue(b, a); findMissingValue(a, b); } private static void findMissingValue(final int[] x, final int[] y) { // loop through the bigger array for (final int n : x) { // for each value in the a array call another loop method to see if it in there if (!findValueSmallerArray(n, y)) { System.out.println("missing value: " + n); // break; } } } private static boolean findValueSmallerArray(final int n, final int[] y) { for (final int i : y) { if (n == i) { return true; } } return false; }