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.