2
\$\begingroup\$

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?

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Simplicity at it's very best, really. Can't get any easier than this. \$\endgroup\$ – Simon Forsberg Aug 17 '14 at 19:05
  • \$\begingroup\$ I just realized that if E does not override hashCode() and equals(), the code will not work well. \$\endgroup\$ – TheCoffeeCup Sep 1 '14 at 0:30
  • \$\begingroup\$ @MannyMeng you need those for your implementation anyway. This code is an improvement on those methods, with the same assumptions. \$\endgroup\$ – Maarten Winkels Sep 1 '14 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.