removeDuplicates method not remove all of the duplicated integers in a list

Question

I am working on an assignment and i have everything working well, I have a list that I have randomly created, and now I have to call a method that removes any duplicated integers in the list. My list size is 100, and when I call my removeDuplicates method it removes most of the duplicates but does not remove all of them. I am wondering if someone can take a look at my method and see why it is doing this. Thanks. Here is my code:

    int size = A.size();
    for (int i = 0; i < size -1; i++) {
        for (int j = i + 1; j < size;) {
            if (A.get(i) == A.get(j)) {
                A.remove(j);
                size--;
            }
            else
                j++;
        }
    }

Here is my full class:

public class Utility {

public static void selectionSort(List<Integer> A) {
    int smIndex, sm;

    for (int i = 0; i < A.size(); i++) {
        sm = A.get(i);
        smIndex = i;

        for (int k = i; k < A.size(); k++) {
            if (sm > A.get(k)) {
                sm = A.get(k);
                smIndex = k;
            }
        }

        if (smIndex == i)
            ;
        else {
            int temp = A.get(i);
            A.set(i, A.get(smIndex));
            A.set(smIndex,  temp);
        }
    }
}

public static void removeDuplicates(List<Integer> A) {
    /*for (int i = 0; i < A.size() -1; i++) {
        for (int j = i + 1; j < A.size();) {
            if (A.get(i) == A.get(j)) {
                A.remove(j);
            }
            else
                j++;
        }
    }*/
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < A.size(); j++) {
                if (i == j) 
                    ;
                else if (A.get(i) == A.get(j)) {
                    A.remove(A.get(j));
                    j = j-1;
                }
                else
                    ;
            }
        }
}

}

This is the test program ( I am just hard coding the 100 for now until i get the remove duplicates figured out):

public class PA1Test extends StopWatch {

public static void main(String[] args) {

    int n = 100;
    List<Integer> list = new Vector<Integer>();

    for (int i = 0; i < n; i++) {
        list.add((int) (Math.random()*2*n));
    }

    start();
    selectionSort(list);
    stop();
    System.out.println("Execution Time: " + getElapsedTime() + " milliseconds");

    if (n > 100) {
        removeDuplicates(list);
        System.out.println(list);
    }
    else {
        System.out.println(list);
        removeDuplicates(list);
        System.out.println(list);
    }


}

}

Answer 1

The problem you've observed is due to a bad == comparison. You mentioned in a comment that the comparison is good up until around 130 and that is correct. == works there because values -128 through 127 are cached so unless they are created explicitly like new Integer(56) they are reference equal. You can do something like the following:

for(int i = 0; i < A.size() - 1; i++) {
    for(int k = i + 1; k < A.size();) {
        if(A.get(i).intValue() == A.get(k).intValue()) {
            A.remove(k);
        } else {
            k++;
        }
    }
}

Note removing items from a list while iterating over it is not considered good practice in Java but you should be OK here. A safer solution is to add the non-duplicates to a new list.

It's also true that if you're looking for an optimization, you will see a solution around here that looks like this:

Set<Integer> set = new LinkedHashSet<Integer>(list);
list.clear();
list.addAll(set);

I have run benchmarks before and it's about 5x faster than iteration despite creating a helper object.

Answer 2

First, you don't need to start your inner loop at 0; start at i+1 instead. Otherwise, you're wasting a lot of time comparing items that have already been compared.

Also, I'm assuming the list isn't sorted.

So:

// Note that A.size() is subject to change, so don't
// cache its value in the loop conditional.
for (int i=0; i<A.size()-1; ++i) {
    // In this loop, we don't always increment j, because
    // removing an item from the list will bring a new item
    // into the j'th position
    for (int j=i+1; j<A.size();) {
        if (A.get(j).equals(A.get(i))) {
            A.remove(j)
        } else {
            ++j;
        }
    }
}

Answer 3

i actually wonder why it would work at all, because you assume that the size of your array is fixed by you are dynamically removing items from it, when you remove items from the List, your List shrinks and what used to be item i is now item i-1, so you keep "skipping" and that's why you can't remove all duplicates the way you are doing it.

loop through the array and add the items to a set, the set by default does not take duplicates so at the end you end-up with unique numbers.

    Set<Integer> hashset = new HashSet<Integer>();
    for (int i = 0; i < A.size(); i++) {
        hashset.add(A.get(i));
    }
    A.clear();
    A.addAll(hashset);