current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
1  
Simplicity at it's very best, really. Can't get any easier than this. –  Simon André Forsberg Aug 17 '14 at 19:05
    
You need to add <E> between private and boolean, or it wouldn't work. –  Manny Meng Aug 17 '14 at 20:02
    
@MannyMeng done, thanks –  Maarten Winkels Aug 17 '14 at 20:04
    
I just realized that if E does not override hashCode() and equals(), the code will not work well. –  Manny Meng Sep 1 '14 at 0:30
    
@MannyMeng you need those for your implementation anyway. This code is an improvement on those methods, with the same assumptions. –  Maarten Winkels Sep 1 '14 at 2:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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