Finding Duplicates in Java

Question

I am trying to figure out a way to make finding duplicates in Java more efficient. I started off with this:

private boolean hasDuplicates(int[] array) {
 List<Integer> list = new ArrayList<Integer>(array.length);
 for(int num : array) {
 list.add(num);
 }
 for(int num : list) {
 if(list.indexOf(num) != list.lastIndexOf(num)) {
 return true;
 }
 }
 return false;
}

But the main problem here is it only can be used if you were to find duplicate numbers. So I made it generic:

private <E> boolean hasDuplicates(E[] array) {
 List<E> list = new ArrayList<E>(array.length);
 for(E e : array) {
 list.add(e);
 }
 for(E e : list) {
 if(list.indexOf(e) != list.lastIndexOf(e)) {
 return true;
 }
 }
 return false;
}

This is what I currently have, but it seems very inefficient, so I tried this:

private static <E> boolean hasDuplicates(E[] array) {
 Arrays.sort(array);
 int length = array.length - 1;
 for(int i = 0; i < length; i++) {
 if(array[i].equals(array[i + 1])) {
 return true;
 }
 }
 return false;
}

But that would throw a ClassCastException if it cannot be cast to java.lang.Comparable during Arrays.sort(). Which returns to the old, inefficient method.

Is there a better solution than this? If so, how?

Answer 1

Use a Set.

private <E> boolean hasDuplicates(E[] array) {
 Set<E> set = new HashSet<E>();
 for(E e : array) {
 if (!set.add(e)) {
 return true;
 }
 }
 return false; 
}

The add() method of a set returns false if the object already exists in the set.

• Simon Forsberg: Simplicity at it's very best, really. Can't get any easier than this.
• TheCoffeeCup: I just realized that if E does not override hashCode() and equals(), the code will not work well.
• Maarten Winkels: @MannyMeng you need those for your implementation anyway. This code is an improvement on those methods, with the same assumptions.